21. [HAOI 2005]希望小学

【问题描述】

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

【输入文件】

第 $1$ 行： $N$ $B_1$ $B_2$ $B_3$ $G_1$ $G_2$ $G_3$ (分别表示村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间)
第 $2$ 行： $X_1$ $X_2$……$X_n$ ($X_i$ 表示第 $i$ 个村要上学的男孩人数)
第 $3$ 行： $Y_1$ $Y_2……Y_n$ ($Y_i$ 表示第 $i$ 个村要上学的女孩人数)
第 $4$ 行： $K$ (道路数)
第 $5 \sim K+4$ 行： $A_i$ $B_i$ $S_{i_1}$ $S_{i_2}$ $S_{i_3}$ (村庄 $A_i$ 到村庄 $B_i$，平路 $S_{i_l}$ 千米，上坡 $S_{i_2}$ 千米，下坡 $S_{i_3}$ 千米,$i=1,2,…，K$)

【输出文件】

$T$（将要建立希望小学村庄的编号）

【数据规模与约定】

$(1) N \leq 30， X_i \leq 20， Y_i \leq 20$;
$(2) K \leq 100$， 每条路的长度 $\leq 30$ 千米;
$(3) B_1，B_2，B_3，G_1，G_2，G_3$ 为整数，都小于 $10$ 个单位时间／每千米;
$(4)$ 每条道路只给出一组数据。例如：$5$ $8$ $7$ $10$ $3$表示从村庄 $5$ 往村庄 $8$ 走，平路有 $7$ 千米，上坡 $10$ 千米。 下坡 $3$ 千米；当然也表示从村庄 $8$ 往村庄 $5$ 走，平路有 $7$ 千米，上坡 $3$ 千米。下坡 $10$ 千米。

【输入输出样例1】

 

hopeschool.in
2 2 2 1 2 3 2
10 12
5 4
1
1 2 10 2 1

hopeschool.out
2

【输入输出样例2】

hopeschool.in
4 3 4 1 4 5 2
8 6 9 4
5 9 8 7
4
1 2 5 6 2
1 3 3 0 2
2 3 6 0 1
3 4 1 2 3

hopeschool.out
3