神奇的硬币II
题号:NC204125
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

StarrySky 有 n 枚神奇的硬币(下标从 1 ~ n),每枚硬币具有固定的价值 val_i 以及融合能量 E_i,同时,商店中有 m 件物品(下标从 1 ~ m),每件物品都有一个固定的重量 w_i。(注:该世界中硬币的价值、融合能量以及物品的重量都有可能为负数。)

在 StarrySky 的世界里,硬币的使用规则与现实世界不同,在他的世界里,只要满足 ,StarrySky 就必须将这枚硬币的融合能量融入这件物品中,成为该物品的能量值,但是,这枚硬币本身并不会被消耗。换句话说,如果当前硬币的价值为 val,融合能量为 E,那么,所有满足 的物品的能量值均会增加 E。

对于同一件物品 i,相同的硬币的能量只能融入这件物品不超过 1 次,但是不影响其它的硬币对这件物品的能量融入,即:1 号硬币的能量可以融入第 i 件物品,同样的,第 n 号硬币的能量也可以融入此件物品,当然前提是都要满足上述要求。

初始状态下,每个物品能量值均规定为 0.

当 n 枚硬币的能量全部融入相应的物品中之后,StarrySky 就可以获得能量值最大的物品(即使该能量值最大的物品实际并没有任何一个硬币的能量融入,StarrySky 也可以获得该物品),如果有多个物品的能量值相同且都是最大值,则 StarrySky 会优先获得序号最小的物品。

现在,StarrySky 希望知道自己能够获得的物品编号是多少?由于 StarrySky 刚在另外一个商店搬完物品,现在汗流浃背,实在写不动程序来解决这个问题,只好向同为 ACMer 的你求救,希望你能帮帮 StarrySky,给出他想要的答案。

输入描述:

第一行输入两个正整数 .

第二行输入 n 个整数 ,表示每个硬币的价值。

第三行输入 n 个整数 ,表示每个硬币的融合能量值。

第四行输入 m 个整数 ,表示每个物品的重量。

输出描述:

输出仅一行一个正整数,表示最终能够获得的物品的编号为多少(物品编号以输入的顺序,从 1 开始顺序编号)。
示例1

输入

复制
5 5
3 5 6 3 8
3 5 6 3 8
3 2 5 1 6

输出

复制
1

说明

初始每个物品能量值分别为:0\ 0\ 0\ 0\ 0
融入第一个硬币的能量后,每个物品的能量值变为:3\ 3\ 0\ 3\ 0
融入第二个硬币的能量后,每个物品的能量值变为:8\ 8\ 5\ 8\ 0
融入第三个硬币的能量后,每个物品的能量值变为:14\ 14\ 11\ 14\ 6
以此类推...
最终,所有物品的能量值分别为:25\ 25\ 19\ 25\ 14
此时,编号为 1, 2, 4 的物品的能量值最大,取编号最小的物品,所以答案为 1