問題
$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