005 - Growing Trees

問題

$N$ 本の木が生えています。
$i \ (1 \leq i \leq N)$ 本目の木を、木 $i$ とします。
各木には成長度という値が設けられており、木 $i$ の現在の成長度は $v_i$ です。
$1$ 日経過するごとに 木 $i$ の成長度は $g_i$ 増加します。
木 $i$ は、成長度が $b_i$ 以上 $w_i$ 以下のとき果実を実らせ、成長度が $w_i$ を超過すると枯れてしまいます。
魔法使いのもけちゃんは次の操作を $0$ 回以上 $M$ 回以下行うことができます。

• 任意の $j \ (1 \leq j \leq N)$ を選び、$g_j$ を $+1$ する。

ここで、すべての木の果実が実っている状態のことを収穫期とします。
適切に操作を行うことで、収穫期の日数を最大化してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$v_1$ $v_2$ $\ldots$ $v_N$
$g_1$ $g_2$ $\ldots$ $g_N$
$b_1$ $b_2$ $\ldots$ $b_N$
$w_1$ $w_2$ $\ldots$ $w_N$

出力

収穫期の日数の最大値を出力せよ。
出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $0 \leq v_i \lt b_i \lt w_i \leq 10^9$
• $1 \leq g_i \leq 10^3$
• 入力は全て整数である。

入出力例

入力例１

3 2
3 1 4
1 1 1
5 8 5
16 18 17

出力例１

7

$1$ 回も操作を行わないのが最適です。すると、今日を $0$ 日目としたときに、
木 $1$： $2$ 日目 ～ $13$ 日目
木 $2$： $7$ 日目 ～ $17$ 日目
木 $3$： $1$ 日目 ～ $13$ 日目
の間果実を実らせるので、収穫期は $7$ 日目 ～ $13$ 日目 の $7$ 日間となります。

---

入力例２

3 2
3 1 4
1 1 1
5 8 5
16 30 17

出力例２

10

$1$ 回、木 $2$ に対して操作を行うのが最適です。すると、今日を $0$ 日目としたときに、
木 $1$： $2$ 日目 ～ $13$ 日目
木 $2$： $4$ 日目 ～ $14$ 日目
木 $3$： $1$ 日目 ～ $13$ 日目
の間果実を実らせるので、収穫期は $4$ 日目 ～ $13$ 日目 の $10$ 日間となります。

---

入力例３

3 0
1 2 3
3 2 1
10 11 12
15 14 13

出力例３

0

操作を行うことができません。今日を $0$ 日目としたときに、
木 $1$： $3$ 日目 ～ $4$ 日目
木 $2$： $5$ 日目 ～ $6$ 日目
木 $3$： $9$ 日目 ～ $10$ 日目
の間果実を実らせるので、収穫期は存在しません。

---

入力例４

18 15
31 13 22 0 18 44 30 25 40 39 34 0 11 8 22 37 38 26
5 6 7 7 3 2 7 5 5 3 8 1 1 3 7 1 1 3
47 40 26 3 53 50 50 38 50 49 49 33 31 55 24 47 43 54
171 156 174 136 172 183 192 145 195 176 154 169 180 177 191 183 146 167

出力例４

9