P8800 [Lanquiao Cup 2022 National B] Cards

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.

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}$.

One line with one integer representing the answer.

**[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