题目描述

小兰和小紫在玩一个塔防游戏 小兰有 $x$ 名士兵。小紫有 $y$ 名士兵。其中$x\lt y$），小兰为了能打赢这场游戏，她决定分配士兵去偷袭小紫的塔防御点，小紫为了保住这些防御点必须派乒进行防守。

假设小紫一共有 $t$ 个没有保护的防御塔，第 $i$ 个防御塔的防守难度系数为 $a_i$，已知小兰最多可派出 $b_i$ 名进攻士兵。这意味着小兰可以投入 $0\sim b_i$ 名士兵来进攻这个防御塔。假如小兰派出了 $z$ 名士兵进攻，那么小紫就需要派出 $z\times a_i$ 名士兵防守，当分配的过程中如果小紫的士兵数量少于 $z\times a_i$ 那么她就只能把剩余的全部士兵都派出到这个防御点，直到士兵用完或者所有的防御塔都防御完。

现在作为小兰的军师，请你帮小兰想出最优的作战方案，使得最后双方部署完后，小兰的剩余兵力多于小紫的剩余兵力，此时请算出这个多余的数量。

输入格式

第一行为三个整数 $x,y,t$。

第二行为 $t$ 个空格隔开的正整数：$a_1\sim a_t$。

第三行为 $t$ 个空格隔开的正整数：$b_1\sim b_t$。

输出格式

最后如果小兰剩余兵力较多，则输出 “小兰的剩余士兵数量”减去“小紫的剩余士兵数量” 的最大值。

否则输出 No。

10 19 3
1 2 3
2 3 5

3

小兰可以给三个防御点分别投入 $0\ 2\ 5$ 名士兵，这样 小紫 就不得不派出 $0\ 4\ 15$ 名士兵才能防守住。最后 小兰 剩余 $10-0-2-5=3$ 名士兵，小紫 没有剩余士兵（$19-0-4-15=0$）。

1 2 1
3
1

No

只有一个防御塔，小兰 可以投入 $1$ 名士兵，小紫就必须把全部的 $2$ 名士兵都派过去。虽然此时 小兰以最小的兵力偷袭成功了这个防御点，但是 小兰分配完士兵后最后手上 剩余的士兵数量并没有大于 小紫 的剩余士兵数量（$0=0$）。所以输出"No".

10 31 4
5 2 4 3
2 2 2 2 

No

小兰可以对四个防御塔各投入 $2$ 名士兵进行偷袭，这样 小紫 就需要 $10+4+8+6=28$ 名士兵防守。最后 小兰 剩余 $10-2-2-2-2=2$ 名士兵，小紫 剩余 $31-28=3$ 名士兵，小兰输。

10 29 4
5 2 4 3
2 2 2 2 

1

$10-2-2-2-2=2$ 名士兵，大于 $29-28=1$ 名士兵。

10 19 4
5 2 4 3
2 2 2 2 

5

其中以一种方案为小兰分别派出 $2\ 1\ 2\ 0$ 名士兵，这样 小紫 需要 $10+2+8+0=20$ 名士兵防守，所有士兵派过去都不够。最后 小兰 剩余 $10-2-1-2-0=5$ 名，小紫 剩余 $0$ 名士兵。

数据规模与约定

对于 $100\%$ 的数据，$1 \le x,y,a_i,b_i \le 10^9$，$1\le t\le 10^3$，$x\lt y$。

• 子任务 1（10 分）：保证 $a_i=1$。
• 子任务 2（20 分）：保证 $t=1, a_1=y$。
• 子任务 3（30 分）：保证 $b_i=x$。
• 子任务 4（40 分）：没有特殊限制。