bzoj#P4700. 适者

适者

题目背景

“虽然不知道那两台是谁干掉的,不过任务完成了。”一一次祖伽密.

题目描述

敌方有 nn 台人形兵器,每台的攻击力为 aia_i,护甲值为 did_i。我方只有一台人形兵器,攻击力为 ATKATK。战斗看作回合制, 每回合进程如下:

  1. 我方选择对方某台人形兵器并攻击,令其护甲值减少 ATKATK,若护甲值 <0<0 则被破坏。
  2. 敌方每台未被破坏的人形兵器攻击我方基地造成 aia_i 点损失。 但是,在第一回合开始之前,某两台敌方的人形兵器被干掉了(秒杀)。问最好情况下,我方基地会受到多少点损失。

输入格式

第一行两个数 nATKn,ATK,表示敌方人形兵器数量和我方人形兵器攻击力。 接下来 nn 行,每行两个数 ai,dia_i,d_i,表示对方第 ii 台人形兵器的攻击力和护甲值。

输出格式

只一行,一个数,表示最好情况下我方基地会受到的损失总和。

样例输入

3 7
30 8
7 35
1 209

样例输出

28

样例说明

最好情况下,被秒杀的是敌方 1,31,3 号人形兵器,接下来需要 55 回合解决对方的 22 号人形兵器,对方共攻击 44 次,总计造成 2828 点伤害。可以证明没有更优的情况。

数据范围与约定

对于 100%100\% 的数据,3n3×1053\le n\le 3×10^5ai,di104a_i,d_i\le 10^4ATK<104ATK<10^4