There Are n Chairs

Vlad has finally become team lead, but he has no time to get home and will have to sleep at the office. Not every IT company can afford a roomy coworking space with a place to nap, so Vlad will sleep on office chairs.

The office has $n$ chairs. The $i$-th chair has height $h_i$ and width $w_i$. Vlad picks any set of chairs $[i_1, i_2, \ldots, i_k]$ and lines them up in a row to lie on. Vlad's height is $H$, so for him to lie down comfortably, the total width of the chosen chairs must be at least $H$:

$\sum\limits_{j=1}^k w_{i_j} \ge H$

Sleeping on chairs of different heights is uncomfortable. The discomfort of a row is the largest height difference between two adjacent chairs in it:

$\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|$

A row with one chair has discomfort $0$. Help Vlad choose chairs so that he can lie down and the discomfort is as small as possible.

The first line contains two integers $n$ and $H$, the number of chairs and Vlad's height ($1 \le n \le 2 \cdot 10^5$; $1 \le H \le 10^9$). The second line contains $n$ integers $h_i$, the chair heights ($1 \le h_i \le 10^9$). The third line contains $n$ integers $w_i$, the chair widths ($1 \le w_i \le 10^9$). It is guaranteed that $H$ does not exceed the sum of all $w_i$.

Print one integer: the minimum possible discomfort among all valid sets.

In the first sample, place chairs 2 and 4 in either order. In the second sample, the sets [1, 5] and [2, 4, 3] both work. Order matters: the row [2, 3, 4] has discomfort $\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2$, which is more than the row [2, 4, 3] gives.