配点: 200 点
問題文
2015年Code FESTIVAL决赛期间,有一个人做了一个滑稽的动作,逗得大家哈哈大笑:“拿着一张写着‘天才’两个字的大纸站起来。”
因此,Code FESTIVAL 2018主赛参赛者 N 大家都做了同样的事情,决定拍一张合影。
每个人都有“漂亮的字迹”和“有趣的面孔”。 2 有两个值, i 此人的“漂亮的字迹”是 a_i,“有趣的面孔” b_i “照片的喜爱度”是所有人的(字迹的美感)x(脸部的趣味性)的总和。
主竞赛的参与者希望最大限度地提高“照片的好感度”。 1 训练两次后,此人的“漂亮字迹”将会提高。 1 上去。
全民培训总次数 X 求照片好感度的最大值(如果必须在 3 次以内)。
小于或等于
制約
- 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 。