問題文

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 以下の整数

入力例 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 より大きくすることはできない.