E - Deck Building
Milk
2
s
1024
MB
100
点
問題文
カードを組み合わせてデッキを構築するゲームを考えます。
$N$ 枚のカードから $M$ 枚を選んでデッキを構築します。各カード $i$ $(1 \le i \le N)$ には、以下の2つの値が設定されています。
- パラメータ $P_i$：カードの基本的な強さ
- リーダースキル効果 $L_i$：リーダーに選ばれたときの倍率
デッキを構築したら、デッキ内の $M$ 枚のカードの中から1枚をリーダーとして選びます。
カード $i$ をリーダーに選んだ場合、デッキ内のすべてのカード（リーダー自身を含む）のパラメータが $L_i$ 倍になります。
デッキの強さは、リーダースキルを適用した後の、デッキ内すべてのカードのパラメータの合計値として定義されます。
デッキの強さが最大になるようにデッキを構築してリーダーを選んだとき、そのデッキの強さの最大値を求めてください。
制約
- $1 \le N \le 10^5$
- $1 \le M \le N$
- $1 \le P_i \le 10^3$ $(1 \le i \le N)$
- $1 \le L_i \le 10^3$ $(1 \le i \le N)$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N~~M$
$P_1~~L_1$
$P_2~~L_2$
$\vdots$
$P_N~~L_N$
- 1行目に、所持カード数 $N$ とデッキに入れるカード数 $M$ が空白区切りで与えられます
- 続く $N$ 行のうち $i$ 行目に、カード $i$ のパラメータ $P_i$ とリーダースキル効果 $L_i$ が空白区切りで与えられます
出力
デッキの強さの最大値を1行で出力してください。
入力例 1
2 2
10 2
20 1
出力例 1
60
カード1とカード2の両方を選択します。リーダーをカード1（$L=2$）にすると $(10 + 20) \times 2 = 60$ となり、これが最大値です。
入力例 2
3 2
100 2
50 3
30 5
出力例 2
650
カード1とカード3を選択し、リーダーをカード3（$L=5$）にすると $(100 + 30) \times 5 = 650$ となり、これが最大値です。
入力例 3
1 1
1000 1
出力例 3
1000
カードが1枚しかないので、それを選んでリーダーにします。$1000 \times 1 = 1000$ です。