Maximum Number of Complete Card Decks

In this problem, you are given n types of cards. For each type i (where i ranges from 1 to n), you initially have a_i cards, each bearing the number i. A complete deck is defined as a set of n cards that contains exactly one card of every type from 1 to n.

Additionally, you have m blank cards. You can write a number on a blank card to transform it into a card of that type. However, for each card type i, you are only allowed to handwrite at most b_i blank cards to convert them into a card of type i.

Your task is to determine the maximum number of complete decks you can form using the available cards and blank cards. Formally, if you want to form K decks, then for each i (1 ≤ i ≤ n), you need K cards of type i. You have a_i cards initially, and you can supplement up to min(b_i, max(0, K - a_i)) blank cards for type i. Moreover, the total number of blank cards used across all types must not exceed m.

The conditions to form K decks are given by:

$$\text{For every } i, \; \max(0, K - a_i) \leq b_i \quad \text{and} \quad \sum_{i=1}^{n} \max(0, K - a_i) \leq m. $$

Find the maximum possible integer K such that these conditions are satisfied.

inputFormat

The input consists of three lines:

1. The first line contains two integers n and m, where 1 ≤ n ≤ 10⁵ (or appropriate constraint) and 0 ≤ m.
2. The second line contains n integers: a₁, a₂, ..., a_n, where a_i is the number of available cards of type i.
3. The third line contains n integers: b₁, b₂, ..., b_n, where b_i is the maximum number of blank cards that can be used for type i.

outputFormat

Output a single integer -- the maximum number of complete decks that can be formed.

sample

3 3
2 1 1
1 1 1

2