AT_code_festival_2018_qualb_b Tensai

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_b CODE FESTIVAL 2015 本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた. そこで, CODE FESTIVAL 2018 本戦参加者の $ N $ 人全員が同じ行動をして, 集合写真を撮ることにした. それぞれの人は「字の綺麗さ」「顔の面白さ」の $ 2 $ つの値を持ち, $ i $ 番目の人の「字の綺麗さ」は $ a_i $, 「顔の面白さ」は $ b_i $ である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる. 本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が $ 1 $ 回トレーニングをすると, この人の「字の綺麗さ」は $ 1 $ 上がる. 全ての人のトレーニング回数の合計を $ X $ 回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.

入力は以下の形式で標準入力から与えられる. > $ N $ $ X $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ a_3 $ $ b_3 $ $ : $ $ : $ $ a_N $ $ b_N $

写真の好感度の最大値を出力しなさい.

### 制約 - $ N $ は $ 1 $ 以上 $ 100 $ 以下の整数 - $ X $ は $ 0 $ 以上 $ 100 $ 以下の整数 - $ a_i,\ b_i\ (1\ \leq\ i\ \leq\ N) $ は $ 1 $ 以上 $ 100 $ 以下の整数 ### Sample Explanation 1 $ 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 $ である. ### Sample Explanation 2 $ X=0 $ なので, 誰もトレーニングできない. したがって, 写真の好感度は $ 25\ \times\ 20\ +\ 17\ \times\ 30\ +\ 9\ \times\ 50\ =\ 1460 $ となる. ### Sample Explanation 3 例えば, $ 1 $ 番目の人が $ 2 $ 回, $ 3 $ 番目の人が $ 1 $ 回トレーニングすると, 写真の好感度 $ 385 $ が達成できる. また, 写真の好感度を $ 385 $ より大きくすることはできない.