問題一覧 > 通常問題

No.818 Dinner time

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 74
作問者 : Enjapma_kyopro / テスター : CuriousFairy315
20 ProblemId : 2986 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-19 23:28:55

問題文

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

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

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

入力

N M
A1 B1
A2 B2
:
AN BN
1≤N≤105
1≤M≤105
−105≤Ai≤105
−105≤Bi≤105
入力はすべて整数

出力

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

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

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