B - DDPC特別ビュッフェⅡ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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 です。
  • このケースは部分点の追加制約を満たしません。