問題一覧 > 通常問題

No.1715 Dinner 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma 👑 ygussanyygussany
11 ProblemId : 7113 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-17 19:35:40

問題文

一人暮らしを始めた Kite_kuma くんは、 これから $D$ 日間夕食の自炊を行うことに決めました。

はじめ、 Kite_kuma くんの元気度は $0$ です。毎日の自炊では、 $N$ 種類の料理の中から一つを選択し、調理した後食べます。$i$ 番目の料理を調理すると元気度が $P_i$ 減少し、その後料理を食べることで元気度が $Q_i$ 増加します。ただし同じ種類の料理を連続で食べると飽きてしまうので、そのような料理の選び方は禁止されています。

Kite_kuma くんは常に元気でいたいので、 $D$ 日間の中での元気度の最小値を最大化するように行動します。
以上の条件のもとで、 $D$ 日間の中での Kite_kuma くんの元気度の最小値を求めてください。ただし Kite_kuma くんの元気度は夕食の自炊でのみ変化するものとします。

制約

  • 入力は全て整数である。
  • $2 \le N,D \le 10^3 $
  • $1 \le P_i,Q_i \le 10^5$

入力

$N$ $D$
$P_1$ $Q_1$
$P_2$ $Q_2$
$\vdots$
$P_N$ $Q_N$

出力

条件のもとでの、$D$ 日間の中での Kite_kuma くんの元気度の最小値を出力してください。

サンプル

サンプル1
入力
2 2
3 3
1 2
出力
-2

$1$ 日目に料理 $2$,$2$ 日目に料理 $1$ を行うことで、 Kite_kuma くんの元気度は

$0 \to -1 \to 1 \to -2\to 1$

と変化します。このとき、元気度の最小値は $-2$ です。

元気度の最小値を $-2$ より大きくすることはできないので、答えは $-2$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。