题目描述

考虑一种有理有据的议会席位分配方法。

假设 $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}$。