No.1715 Dinner 2
タグ : / 解いたユーザー数 72
作問者 :
nok0
/ テスター :
zkou
Kite_kuma
ygussany
問題文
一人暮らしを始めた 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もしくは右上の雲マークをクリックしてアカウントを作成してください。