問題文

DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のDDPC特別ビュッフェの時間が始まりました。あなたはこれから料理の載っていないトレーに料理を載せに行くところです。 DDPC特別ビュッフェには $N$ 種類の料理があります。 $i$ 種類目の料理はビュッフェの開始から $T_i$ 秒後になくなり、料理の美味しさは $A_i$ です。

DDPC特別ビュッフェにはいくつかの特別なルールがあります。

• あなたは $1$ 種類の料理をトレーに載せるのに $1$ 秒かけなくてはならない。すなわち料理を載せ始めた時刻が $s$ であったとき、料理を載せ終わったときの時刻は $s+1$ となる。
• あなたは以前にトレーに載せた料理と同じ種類の料理を載せてはならない。
• 現在の時刻 $s$ が$s+1≦T_i$ を満たさないとき、種類 $i$ の料理をトレーに載せることはできない。

あなたはトレーに載っている料理の美味しさの総和が $X$ 以上になったところで席に戻ることにしました。トレーに載っている料理の美味しさの総和を $X$ 以上にすることが可能な最小の時刻 $t$ を求めてください。

---

入力

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

$N$ $X$ $T_1$ $T_2$ … $T_N$ $A_1$ $A_2$ … $A_N$

• $1$ 行目にDDPC特別ビュッフェに存在する料理の種類数を表す整数 $N(1≦N≦10^{5})$ とトレーに載っている料理の美味しさの総和の目標値 $X(1≦X≦10^{9})$ が空白区切りで与えられる。
• $2$ 行目にDDPC特別ビュッフェに存在する料理の $i$ 種類目の料理がなくなる時刻 $T_i (1≦T_i≦10^{5})$ が空白区切りで与えられる。
• $3$ 行目にDDPC特別ビュッフェに存在する料理の $i$ 種類目の料理の美味しさを表す整数 $A_i (1≦A_i≦10^{5})$ が空白区切りで与えられる。

出力

トレーに載っている料理の美味しさの総和を $X$ 以上にすることが可能な最小の時刻 $t$ を $1$ 行に出力せよ。不可能な場合は-1を出力せよ。末尾に改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $T_i<T_j$ のとき、$A_i≧A_j$ を満たすようなデータセットに正解した場合 $10$ 点が与えられる。
• 追加制約のないデータセットに正解した場合さらに $40$ 点が得られ合計 $50$ 点が得られる。

---

入力例 1

4 5
1 2 3 4
3 3 1 1

出力例 1

2

• 以下のような料理の取り方をすることで、時刻 $2$ にトレーに載っている料理の美味しさの総和が $5$ 以上にすることが可能です。
• $0$ 秒目の時点でトレーに載っている料理の美味しさの総和は $0$ です。種類 $1$ の料理をトレーに載せます。
• $1$ 秒目の時点でトレーに載っている料理の美味しさの総和は $3$ です。種類 $2$ の料理をトレーに載せます。
• $2$ 秒目の時点でトレーに載っている料理の美味しさの総和は $6$ です。
• このケースは部分点の追加制約を満たします。

---

入力例 2

3 10
1 2 3
3 3 4

出力例 2

3

• 以下のような料理の取り方をすることで、時刻 $3$ にトレーに載っている料理の美味しさの総和が $10$ 以上にすることが可能です。
• $0$ 秒目の時点でトレーに載っている料理の美味しさの総和は $0$ です。種類 $1$ の料理をトレーに載せます。
• $1$ 秒目の時点でトレーに載っている料理の美味しさの総和は $3$ です。種類 $2$ の料理をトレーに載せます。
• $2$ 秒目の時点でトレーに載っている料理の美味しさの総和は $6$ です。種類 $3$ の料理をトレーに載せます。
• $3$ 秒目の時点でトレーに載っている料理の美味しさの総和は $10$ です。
• このケースは部分点の追加制約を満たしません。

---

入力例 3

3 5
9 9 4
2 2 6

出力例 3

1

• 以下のような料理の取り方をすることで、時刻 $1$ にトレーに載っている料理の美味しさの総和が $5$ 以上にすることが可能です。
• $0$ 秒目の時点でトレーに載っている料理の美味しさの総和は $0$ です。種類 $3$ の料理をトレーに載せます。
• $1$ 秒目の時点でトレーに載っている料理の美味しさの総和は $6$ です。
• このケースは部分点の追加制約を満たします。

---

入力例 4

5 101
1 2 3 4 5
20 20 20 20 20

出力例 4

-1

• どのように料理をとっても、トレーに載っている料理の美味しさの総和を $101$ 以上にすることはできません。
• このケースは部分点の追加制約を満たします。

---

入力例 5

2 2
1 1
1 1

出力例 5

-1

• 時刻 $0$ でどちらの料理をとっても、もう片方の料理が時刻 $1$ でなくなってしまうため、トレーに載っている料理の美味しさを $2$ 以上にすることはできません。
• このケースは部分点の追加制約を満たします。

---

入力例 6

4 6
1 1 2 2
3 4 1 2

出力例 6

2

• 以下のような料理の取り方をすることで、時刻 $2$ にトレーに載っている料理の美味しさの総和が $6$ 以上にすることが可能です。
• $0$ 秒目の時点でトレーに載っている料理の美味しさの総和は $0$ です。種類 $2$ の料理をトレーに載せます。
• $1$ 秒目の時点でトレーに載っている料理の美味しさの総和は $4$ です。種類 $4$ の料理をトレーに載せます。
• $2$ 秒目の時点でトレーに載っている料理の美味しさの総和は $6$ です。
• このケースは部分点の追加制約を満たします。

---

入力例 7

3 4
1 2 2
1 2 2

出力例 7

2

• 以下のような料理の取り方をすることで、時刻 $2$ にトレーに載っている料理の美味しさの総和が $4$ 以上にすることが可能です。
• $0$ 秒目の時点でトレーに載っている料理の美味しさの総和は $0$ です。種類 $2$ の料理をトレーに載せます。
• $1$ 秒目の時点でトレーに載っている料理の美味しさの総和は $2$ です。種類 $3$ の料理をトレーに載せます。
• $2$ 秒目の時点でトレーに載っている料理の美味しさの総和は $4$ です。
• このケースは部分点の追加制約を満たしません。

---