配点: $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$ より大きくすることはできない.