Problem Description

On this day, Xiaoming is organizing his cards.

He has a total of $n$ types of cards. On the $i$-th type of card, a positive integer $i \ (i \in [1, n])$ is printed, and he currently has $a_{i}$ cards of type $i$.

If there are $n$ cards with exactly one card of each type, then these $n$ cards are called one set. In order to make as many sets as possible, Xiaoming takes out $m$ blank cards. He can write the number $i$ on a blank card and treat it as a card of type $i$ to form sets. However, Xiaoming feels that handwritten cards do not look nice, so he decides to handwrite at most $b_{i}$ cards of type $i$.

Please find the maximum number of sets Xiaoming can form.

Input Format

The input has 3 lines.

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

The second line contains $n$ positive integers $a_{1}, a_{2}, \ldots, a_{n}$.

The third line contains $n$ positive integers $b_{1}, b_{2}, \ldots, b_{n}$.

Output Format

One line with one integer representing the answer.

4 5
1 2 3 4
5 5 5 5

3

Hint

[Sample Explanation]

Among these $5$ blank cards, take $2$ cards to write $1$, and take $1$ card to write $2$. Then the number of each type of card becomes $3, 3, 3, 4$, so you can form $3$ sets. The remaining $2$ blank cards can no longer help Xiaoming form another set.

[Test Case Scale and Assumptions]

For $30\%$ of the testdata, it is guaranteed that $n \leq 2000$.

For $100\%$ of the testdata, it is guaranteed that $n \leq 2 \times 10^{5}; \ a_{i}, b_{i} \leq n; \ m \leq n^{2}$.

Lanqiao Cup 2022 National Contest Group B, Problem C.

Translated by ChatGPT 5