/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君の果樹園には 1 から N までの番号が付けられた N 本の木があり、各木には果物が 1 つ実っています。
木 i の果物は、1 日目における美味しさが A_i であり、1 日が経過するごとに美味しさが D_i ずつ減少します。
高橋君は 1 日目から K 日目までの K 日間、毎日、まだ果物を収穫していない木を 1 本選んでその果物を収穫します。
t 日目（1 \leq t \leq K）に木 i の果物を収穫したとき、得られる果物の美味しさは \max(0, A_i - (t - 1) \times D_i) となります。
高橋君が収穫した K 個の果物の美味しさの合計として考えられる最大値を求めてください。
制約
- 1 \leq K \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- 0 \leq D_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 D_1 A_2 D_2 \vdots A_N D_N
出力
高橋君が収穫した K 個の果物の美味しさの合計として考えられる最大値を 1 行で出力してください。
入力例 1
3 2 10 3 8 1 5 0
出力例 1
17
入力例 2
4 3 20 10 15 2 10 1 5 0
出力例 2
41
入力例 3
10 6 100 15 50 2 80 20 200 50 30 0 120 10 90 25 60 5 150 40 110 30
出力例 3
550
入力例 4
20 12 1000000000 50000000 850000000 30000000 920000000 40000000 400000000 10000000 600000000 20000000 750000000 35000000 300000000 5000000 950000000 45000000 500000000 15000000 880000000 25000000 200000000 0 650000000 18000000 700000000 22000000 800000000 32000000 450000000 12000000 990000000 60000000 550000000 16000000 350000000 8000000 900000000 28000000 250000000 2000000
出力例 4
8258000000
入力例 5
1 1 1000000000 1000000000
出力例 5
1000000000
Score : 433 pts
Problem Statement
Takahashi's orchard has N trees, numbered 1 through N. Each tree bears one fruit.
The fruit on tree i has a deliciousness of A_i on day 1, and its deliciousness decreases by D_i each day that passes.
For the K days from day 1 to day K, Takahashi will choose one tree each day from which he has not yet harvested a fruit, and harvest its fruit.
If he harvests the fruit of tree i on day t (1 \leq t \leq K), the deliciousness of the obtained fruit will be \max(0, A_i - (t - 1) \times D_i).
Find the maximum possible total deliciousness of the K fruits harvested by Takahashi.
Constraints
- 1 \leq K \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- 0 \leq D_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 D_1 A_2 D_2 \vdots A_N D_N
Output
Print the maximum possible total deliciousness of the K fruits harvested by Takahashi in a single line.
Sample Input 1
3 2 10 3 8 1 5 0
Sample Output 1
17
Sample Input 2
4 3 20 10 15 2 10 1 5 0
Sample Output 2
41
Sample Input 3
10 6 100 15 50 2 80 20 200 50 30 0 120 10 90 25 60 5 150 40 110 30
Sample Output 3
550
Sample Input 4
20 12 1000000000 50000000 850000000 30000000 920000000 40000000 400000000 10000000 600000000 20000000 750000000 35000000 300000000 5000000 950000000 45000000 500000000 15000000 880000000 25000000 200000000 0 650000000 18000000 700000000 22000000 800000000 32000000 450000000 12000000 990000000 60000000 550000000 16000000 350000000 8000000 900000000 28000000 250000000 2000000
Sample Output 4
8258000000
Sample Input 5
1 1 1000000000 1000000000
Sample Output 5
1000000000