No.818 Dinner time
タグ : / 解いたユーザー数 75
作問者 :
Enjapma_kyopro
/ テスター :
CuriousFairy315
問題文
あなたは、$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
答えが非常に大きくなる場合があることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。