万里ACM discuss3

Description

有 $n$ 棵树，初始时每棵树的高度为 $H_i$ ，第 $i$ 棵树每月都会长高 $A_i$ 。现在有个木料长度总量为 $S$ 的订单，客户要求每块木料的长度不能小于 $L$ ，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足订单。

Input

第一行 $3$ 个用空格隔开的非负整数 $n, S, L$ ，表示树的数量、订单总量和单块木料长度限制。

第二行 $n$ 个用空格隔开的非负整数，依次为 $H_{1}, H_{2}, \dots, H_{n}$ 。

第三行 $n$ 个用空格隔开的非负整数，依次为 $A_{1}, A_{2}, \dots, A_{n}$ 。

Output

输出一行一个整数表示答案。

Sample Input Copy

3 74 51
2 5 2
2 7 9

Sample Output Copy

HINT

测试点编号	$n$	特殊约定
1	$n = 1$	$\leq S \leq H_i \leq 10000$
2	$n = 1$	$\leq S, L, H_i, A_i \leq 10000$
3	$\leq n \leq 1000$
4
5
6		$\leq S, L, H_i, A_i \leq 10^9$
7
8
9	$\leq n \leq 20000$
10
11		$\leq S, L \leq 10^{18}$ ， $\leq H_i, A_i \leq 10^9$
12		$\leq S, L \leq 10^{18}$ ， $\leq H_i, A_i \leq 10^9$
13	$\leq n \leq 200000$	$L = 1$
14		$\leq L$
15		$\leq S, L \leq 10^{18}$ ， $\leq H_i, A_i \leq 10^9$
16
17
18
19
20

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。
Credit：idea/郑林楷　命题/郑林楷　验题/王聿中
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。

Source/Category

LibreOJ