Trait Growth Leap

'MapleStory' has a system called 'traits'. Raising the levels of traits such as 'Charisma', 'Charm', and 'Craftsmanship' lets you build up the abilities assigned to each trait. Jihun has played this game for a long time, so every trait on his main character is at max level. When all trait levels are equal, the trait graph becomes a regular polygon, as in the picture below.

A trait level is raised with 'trait items'. To raise any trait from level $x$ to level $x+1$, you need $x$ of that trait's items. Alternatively, the special trait item 'Growth Leap' raises the level of any chosen trait by exactly $1$. A trait at max level cannot use a trait item, so Jihun decided to move his spare trait items to storage and use them to raise trait levels on another character.

The character that will use the trait items has $N$ traits, and the traits have no max level, so their levels can keep rising. Jihun also likes large regular polygons, so he wants the trait graph of this character to be the largest regular $N$-gon possible. Given the number of Growth Leaps $M$, the current level of each trait, and the number of trait items for each trait, find the size of the largest regular $N$-gon Jihun can make, that is, the highest level at which a regular $N$-gon can be formed.

The first line contains two integers $N$ and $M$, separated by a space. ($3 \leq N \leq 100\,000$; $0 \leq M \leq 10^{12}$)

The second line contains $N$ integers $L_1, L_2, \cdots , L_N$, separated by spaces, giving the current level of each trait. ($1 \leq L_i \leq 10^9$)

The third line contains $N$ integers $A_1, A_2, \cdots , A_N$, separated by spaces, giving the number of trait items for each trait. ($0 \leq A_i \leq 10^{18}$)

Print the size of the largest regular $N$-gon Jihun can make, that is, the highest level at which a regular $N$-gon can be formed.

If no regular polygon can be formed, print -1.

Log in to MapleStory and look for the hidden item in this problem!