CODE FESTIVAL 2018 qual B

B - Tensai


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点: 200

問題文

CODE FESTIVAL 2015 本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた.
そこで, CODE FESTIVAL 2018 本戦参加者の N 人全員が同じ行動をして, 集合写真を撮ることにした.

それぞれの人は「字の綺麗さ」「顔の面白さ」の 2 つの値を持ち, i 番目の人の「字の綺麗さ」は a_i, 「顔の面白さ」は b_i である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる.

本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が 1 回トレーニングをすると, この人の「字の綺麗さ」は 1 上がる.
全ての人のトレーニング回数の合計を X 回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.

制約

  • N1 以上 100 以下の整数
  • X0 以上 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 より大きくすることはできない.


Submit提出する