Consider a well-founded method for allocating parliamentary seats.

Suppose there are $n$ political parties with final vote counts $V_i$, and $m$ seats to be allocated. The rules are as follows:

The parliament is initially empty, and each party has $0$ seats.

For each party, calculate $Q_i = \frac{V_i}{S_i+1}$, where $S_i$ denotes the number of seats already obtained by the $i$-th party. The party $p$ with the largest $Q_i$ is chosen. If multiple parties have the same $Q_i$, the one with the smallest index is chosen.

Allocate one seat to party $p$, and repeat the previous step until all $m$ seats are allocated.

Voting is currently in progress. Each party has a current vote count $v_i$, and there are $n$ groups of voters who have not yet cast their ballots. The $i$-th group has $a_i$ people, and each person in this group can choose to vote for either party $i$ or party $i+1$ (with party $n+1$ being party $1$). No abstentions are allowed.

Calculate the maximum number of seats the first party can obtain.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers representing $v_i$.

The next line contains $n$ integers representing $a_i$.

Output

A single integer representing the answer.

Examples

Input 1

3 3
10 5 6
3 1 2

Output 1

2

Input 2

5 5
2 1 3 3 3
2 4 2 5 5

Output 2

2

Constraints

For all data: $2 \le n \le 10^5, m \le 10^9, v_i, a_i \le 10^9, v_i > 0$.

Subtask 1 (10 pts): $n, m \le 5, v_i, a_i \le 5$.

Subtask 2 (10 pts): $n \le 50, m \le 100, v_i, a_i \le 250$.

Subtask 3 (20 pts): $n \le 50, m \le 500$.

Subtask 4 (20 pts): $n \le 1000, m \le 1000$.

Subtask 5 (20 pts): $n \le 10^4$.

Subtask 6 (20 pts): No special restrictions.