[HAOI2005]希望小学

Grade 0 Open Time Wednesday, 16 January 2013, 10:55 am
Discount 0.8 Time Discount Wednesday, 16 January 2013, 10:55 am
Allow late Yes Close Time Wednesday, 16 January 2013, 10:55 am
Input file hopeschool.in Output file hopeschool.out


【问题描述】


地处偏僻山区的X乡有N个自然村,目前还没有一所小学,孩子们要么不上学,要么需要翻过一座大山到别处上学。如今好啦,有一位热心人士准备捐款在某个自然村建立一所希望小学。
通过调查发现,X乡各个村庄之间的道路较为复杂,有平路、上坡和下坡。考虑到每个村孩子们的人数不同,走上坡、下坡和平路的速度也不同,?男孩和女孩走路速度也不同,请你为X乡选择一个最合适建立希望小学的村庄,使得所有的孩子花在路上的总时间最少。


【输入文件】


hopeschool.in

第1行: N B1 B2 B3 G1 G2 G3 (村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间)
第2行: Xl X2……Xn (Xi表示第i个村要上学的男孩人数)
第3行: Y1 Y2……Yn (Yi表示第i个村要上学的女孩人数)
第4行: K (道路数)
第5—K+4行: Ai Bi Si1 Si2 Si3 (村庄Ai到村庄Bi,平路Sil千米,上坡Si2千米,下坡Si3千米,i=1,2,…,K)


【输出文件】


hopeschool.out

T(将要建立希望小学村庄的编号)


【约束条件】


(1) N<=30, Xi<=20, Yi<=20
(2) K<=100, 每条路的长度<=30千米
(3) B1,B2,B3,G1,G2,G3为整数,都小于10个单位时间/每千米
(4) 每条道路只给出一组数据。例如:5 8 7 10 3表示从村庄5往村庄8走,平路
有7千米,上坡10千米。 下坡3千米;当然也表示从村庄8往村庄5走,平路有7千米,
上坡3千米。下坡10千米。


【输入输出样例】


hopeschool.in

2 2 2 1 2 3 2
10 12
5 4
1
1 2 10 2 1

hopeschool.out

2