You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

共敌不如分敌，敌阳不如敌阴。

题目描述

33DAI 有 $n$ 名士兵。Kitten 有 $m$ 名士兵。33DAI 的士兵数量小于 Kitten 的（$n\lt m$），为了避免被 Kitten 打败，33DAI 决定分配士兵去攻击 Kitten 的资源点，让 Kitten 不得不分配士兵去防守资源点。

Kitten 一共有 $k$ 个没有保护的资源点，第 $i$ 个资源点的防守难度为 $a_i$，最多容纳 $b_i$ 名进攻士兵。这意味着 33DAI 可以投入 $0\sim b_i$ 名士兵来进攻这个资源点。如果 33DAI 派出了 $num$ 名士兵攻击，Kitten 就需要安排 $num\times a_i$ 名士兵防守，假设此时 Kitten 的士兵数量少于 $num\times a_i$ 那么她有多少士兵就会派出多少士兵。

请问 33DAI 能否通过分配士兵攻击资源点，逼迫 Kitten 防守，来让 Kitten 的剩余士兵数量小于 33DAI 的剩余士兵数量。

输入格式

第一行为三个整数 $n,m,k$。

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

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

输出格式

如果能让 Kitten 的剩余士兵数量小于 33DAI 的剩余士兵数量，输出 “33DAI 的剩余士兵数量”减去“Kitten 的剩余士兵数量” 的最大值。

否则输出 No。

10 19 3
1 2 3
2 3 5

3

33DAI 可以给三个资源点分别投入 $0\ 2\ 5$ 名士兵，这样 Kitten 就需要 $0\ 4\ 15$ 名士兵才能防守住。最后 33DAI 剩余 $10-0-2-5=3$ 名士兵，Kitten 没有剩余士兵（$19-0-4-15=0$）。

1 2 1
3
1

No

只有一个资源点，33DAI 可以投入 $1$ 名士兵，这样 Kitten 就会把剩下的 $2$ 名士兵都派过去。虽然此时 33DAI 拿下了这个资源点，但是 Kitten 的剩余士兵数量并没有少于 33DAI 的剩余士兵数量（$0=0$）。

10 31 4
5 2 4 3
2 2 2 2 

No

33DAI 可以给四个资源点各投入 $2$ 名士兵，这样 Kitten 就需要 $10+4+8+6=28$ 名士兵防守。最后 33DAI 剩余 $10-2-2-2-2=2$ 名士兵，Kitten 剩余 $31-28=3$ 名士兵。

10 29 4
5 2 4 3
2 2 2 2 

1

33DAI 可以给四个资源点各投入 $2$ 名士兵，这样 Kitten 就需要 $10+4+8+6=28$ 名士兵防守。最后 33DAI 剩余 $10-2-2-2-2=2$ 名士兵，Kitten 剩余 $29-28=1$ 名士兵。

10 19 4
5 2 4 3
2 2 2 2 

5

33DAI 可以给四个资源点分别投入 $2\ 1\ 2\ 0$ 名士兵，这样 Kitten 就需要 $10+2+8+0=20$ 名士兵防守，所有士兵派过去都不够。最后 33DAI 剩余 $10-2-1-2-0=5$ 名士兵，Kitten 剩余 $0$ 名士兵。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m,a_i,b_i \le 10^9$，$1\le k\le 10^3$，$n\lt m$。

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