No.818 Dinner time

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 49
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : CuriousFairy315CuriousFairy315
13 ProblemId : 2986 / 出題時の順位表

問題文

あなたは、$N$ 匹のニワトリを飼っています。このニワトリ達には、それぞれ $1$ 番から $N$ 番まで番号が付いています。
あなたは、Enjapma 王国に滞在している $M$ 日間のあいだ、ニワトリ達の力を借りて晩ごはんを作ることに決めました。
$i$ $(1 \le i \le M)$ 日目の晩ごはんは、以下の要領で作ることにします。

$1$ .整数 $K$ $(1 \le K \le N)$ の値を決める。
$2$ .$1$ 番から $K$ 番までのまだ鶏肉になっていないニワトリ全てについて、以下の操作のうちどちらかを選び、食材を得る。
  ・タマゴを産ませる。$i$ 番のニワトリが産むタマゴの「美味しさ」は $A_i$ である。
  ・鶏肉にする。$i$ 番のニワトリが鶏肉になったときの「美味しさ」は $B_i$ である。
$3$ .この日に得た食材(タマゴと鶏肉)を全て使って、晩ごはんを作る。晩ごはんの「美味しさ」は、使った全ての食材の「美味しさ」の総和である。

さて、$M$ 日間の晩ごはんの「美味しさ」の総和を最大化してください。

入力

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_N$ $B_N$
$1 \le N \le 10^5$
$1 \le M \le 10^5$
$-10^5 \le A_i \le 10^5$
$-10^5 \le B_i \le 10^5$
入力はすべて整数

出力

$M$ 回の晩ごはんの「美味しさ」の総和の最大値を求めてください。
最後に改行してください。

サンプル

サンプル1
入力
3 3
2 5
-3 -8
1 10
出力
16

$1$ 日目は、$K$ $=$ $3$ とします。$1$ 番と $2$ 番のニワトリにタマゴを産ませ、$3$ 番目のニワトリを鶏肉にします。
$2$ 日目は、$K$ $=$ $1$ として、$1$ 番のニワトリにタマゴを産ませます。
$3$ 日目は、$K$ $=$ $1$ として、$1$ 番のニワトリを鶏肉にします。

サンプル2
入力
2 2
-3 10
-2 5
出力
15

$1$ 日目は、$K$ $=$ $2$ とします。$1$ 番と $2$ 番のニワトリを鶏肉にします。
$2$ 日目は、$K$ $=$ $2$ とします。しかし、$1$ 番と $2$ 番のニワトリはどちらも鶏肉になったので、この日は食材を得られません。

サンプル3
入力
5 50000
10000 1
20000 2
30000 3
40000 4
50000 5
出力
7500000000

答えが非常に大きくなる場合があることに注意してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。