AT_code_festival_2018_final_f Dinner Planning

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-final/tasks/code_festival_2018_final_f 高橋君の冬休みは $ N $ 日あります。 高橋君は $ N $ 日間の食事の予定を考えています。 $ i $ 日目の予定は $ T_i $ が $ 0 $ ならばラーメン屋に行く予定であり、 $ T_i $ が $ 1 $ ならばレストランに行く予定です。食事の美味しさは $ A_i $ です。 高橋君には *グルメ度* があり、はじめグルメ度は $ 0 $ です。 高橋君がラーメン屋でご飯を食べた場合、グルメ度は $ 1 $ **減少** します。 高橋君がレストランでご飯を食べた場合、グルメ度は $ 1 $ **増加** します。 高橋君はグルメ度を $ 0 $ 以上 $ K $ 以下に保ちたいです。 高橋君は $ 0 $ 個以上の食事の予定をキャンセルし、自炊をすることができます。自炊をした場合、グルメ度は変化せず、食事の美味しさは $ 0 $ です。 高橋君が冬休みで得られる美味しさの総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T_1 $ $ A_1 $ $ : $ $ T_{N} $ $ A_{N} $

答えを出力せよ。

### 制約 - $ 1\ \leq\ K\ \leq\ N\ \leq\ 10^{5} $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ T_i $ は `0` あるいは `1` - 与えられる入力は全て整数 ### Sample Explanation 1 \- $ 1 $ 日目：自炊をする。グルメ度は $ 0 $ のままです - $ 2 $ 日目：レストランに行く。グルメ度は $ 1 $ になります - $ 3 $ 日目：ラーメン屋に行く。グルメ度は $ 0 $ になります - $ 4 $ 日目：レストランに行く。グルメ度は $ 1 $ になります - $ 5 $ 日目：レストランに行く。グルメ度は $ 2 $ になります - $ 6 $ 日目：ラーメン屋に行く。グルメ度は $ 1 $ になります - $ 7 $ 日目：自炊をする。グルメ度は $ 1 $ のままです - $ 8 $ 日目：ラーメン屋に行く。グルメ度は $ 0 $ になります - 得られる食事の美味しさの総和は $ 7+2+8+4+6+4\ =\ 31 $ となり、これが最大です。 ### Sample Explanation 3 \- 答えが大きくなりうることに注意してください