No.818 Dinner time
タグ : / 解いたユーザー数 79
作問者 :
Enjapma_kyopro
/ テスター :
CuriousFairy315
Problem Statement
You keep $N$ chickens. The chickens are numbered from $1$ to $N$.
You have decided to make dinner with the help of the chickens during the $M$ days you are staying in the Kingdom of Enjapma.
The dinner on day $i$ $(1 \le i \le M)$ is made as follows.
$1$ . Decide the value of an integer $K$ $(1 \le K \le N)$.
$2$ . For every chicken numbered from $1$ to $K$ that has not yet been turned into chicken meat, choose one of the following operations to obtain an ingredient.
・Have it lay an egg. The "deliciousness" of an egg laid by chicken $i$ is $A_i$.
・Turn it into chicken meat. The "deliciousness" of chicken $i$ when turned into chicken meat is $B_i$.
$3$ . Make dinner using all the ingredients (eggs and chicken meat) obtained on that day. The "deliciousness" of the dinner is the sum of the "deliciousness" of all the ingredients used.
Maximize the sum of the "deliciousness" of the dinners over the $M$ days.
Input
$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$
All inputs are integers.
Output
Output the maximum possible sum of the "deliciousness" of the $M$ dinners.
Print a newline at the end.
Sample
Sample 1
Input
3 3
2 5
-3 -8
1 10
Output
16
On day $1$, let $K$ $=$ $3$. Have chickens $1$ and $2$ lay eggs, and turn chicken $3$ into chicken meat.
On day $2$, let $K$ $=$ $1$, and have chicken $1$ lay an egg.
On day $3$, let $K$ $=$ $1$, and turn chicken $1$ into chicken meat.
Sample 2
Input
2 2
-3 10
-2 5
Output
15
On day $1$, let $K$ $=$ $2$. Turn chickens $1$ and $2$ into chicken meat.
On day $2$, let $K$ $=$ $2$. However, since chickens $1$ and $2$ have both been turned into chicken meat, no ingredients are obtained on this day.
Sample 3
Input
5 50000
10000 1
20000 2
30000 3
40000 4
50000 5
Output
7500000000
Note that the answer can be very large.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。