题目描述
考虑一种有理有据的议会席位分配方法。
假设 $n$ 个政党的最终票分别为 $V_i$，分配 $m$ 个席位，规则如下：
初始议会为空，每个政党有 $0$ 个席位。
对于每个政党，计算 $Q_i = \frac{V_i}{S_i+1}$ 最大的政党 $p$, 其中 $S_i$ 表示第 $i$ 个政党已经获得的席位。若有多个政党 $Q_i$ 相同，取编号最小的那个。
分配给政党 $p$ 一个席位，重复上步，直到分配完 $m$ 个席位。
现在投票还在进行，每个政党当前得票数为 $v_i$，还有 $n$ 堆群众未进行投票，其中第 $i$ 堆群众人数为 $a_i$，且其中每个人可以选择投给第 $i$ 或 $i + 1$ 个政党，不能弃权。特殊的，第 $n$ 堆群众可以投给第 $n$ 和 $1$ 个政党。
请计算第 $1$ 个政党最多能获得多少个席位。
输入格式
第一行两个整数 $n,m$。
接下来一行 $n$ 个整数表示 $v_i$。
接下来一行 $n$ 个整数 $a_i$。
输出格式
一个整数表示答案。
样例输入1
3 3
10 5 6
3 1 2样例输出1
2样例输入2
5 5
2 1 3 3 3
2 4 2 5 5样例输出2
2数据范围
对于所有数据：$2 \le n \le 10^5,m \le 10^9,v_i,a_i \le 10^9,v_i>0$。
$\text{Subtask 1 (10 pts)}$：$n,m \le 5,v_i,a_i \le 5$。
$\text{Subtask 2 (10 pts)}$：$n \le 50,m \le 100,v_i,a_i \le 250$。
$\text{Subtask 3 (20 pts)}$：$n \le 50,m \le 500$。
$\text{Subtask 4 (20 pts)}$：$n \le 1000,m \le 1000$。
$\text{Subtask 5 (20 pts)}$：$n \le 10^4$。
$\text{Subtask 6 (20 pts)}$：无特殊限制。
时间限制：$\text{1s}$。
空间限制：$\text{256MB}$。