Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 200 点
問題文
CODE FESTIVAL 2015 本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた.
そこで, CODE FESTIVAL 2018 本戦参加者の N 人全員が同じ行動をして, 集合写真を撮ることにした.
それぞれの人は「字の綺麗さ」「顔の面白さ」の 2 つの値を持ち, i 番目の人の「字の綺麗さ」は a_i, 「顔の面白さ」は b_i である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる.
本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が 1 回トレーニングをすると, この人の「字の綺麗さ」は 1 上がる.
全ての人のトレーニング回数の合計を X 回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.
制約
- N は 1 以上 100 以下の整数
- X は 0 以上 100 以下の整数
- a_i, b_i \ (1 \leq i \leq N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N X a_1 b_1 a_2 b_2 a_3 b_3 : : a_N b_N
出力
写真の好感度の最大値を出力しなさい.
入力例 1
3 1 12 10 24 20 36 5
出力例 1
800
X=1 なので, トレーニングできる回数は 1 回までである. したがって, 次の 4 通りの方法が考えられる.
- 誰もトレーニングしない場合:写真の好感度は 12 \times 10 + 24 \times 20 + 36 \times 5 = 780
- 1 番目の人が 1 回トレーニングする場合:写真の好感度は 13 \times 10 + 24 \times 20 + 36 \times 5 = 790
- 2 番目の人が 1 回トレーニングする場合:写真の好感度は 12 \times 10 + 25 \times 20 + 36 \times 5 = 800
- 3 番目の人が 1 回トレーニングする場合:写真の好感度は 12 \times 10 + 24 \times 20 + 37 \times 5 = 785
よって, 写真の好感度の最大値は 800 である.
入力例 2
3 0 25 20 17 30 9 50
出力例 2
1460
X=0 なので, 誰もトレーニングできない. したがって, 写真の好感度は 25 \times 20 + 17 \times 30 + 9 \times 50 = 1460 となる.
入力例 3
3 3 3 25 5 12 7 25
出力例 3
385
例えば, 1 番目の人が 2 回, 3 番目の人が 1 回トレーニングすると, 写真の好感度 385 が達成できる.
また, 写真の好感度を 385 より大きくすることはできない.