F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 4700. -- 适者

4700: 适者

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 351  Solved: 138
[Submit][Status][Discuss]

Description

【题目背景】
“虽然不知道那两台是谁干掉的,不过任务完成了。”一一次祖伽密.
【题意描述】
敌方有n台人形兵器,每台的攻击力为Ai,护甲值为Di。我方只有一台人形兵器,攻击力为ATK。战斗看作回合制,
每回合进程如下:
  ·1 我方选择对方某台人形兵器并攻击,令其护甲值减少ATK,
若护甲值<0则被破坏。
  ·2 敌方每台未被破坏的人形兵器攻击我方基地造成Ai点损失。
但是,在第一回合开始之前,某两台敌方的人形兵器被干掉了(秒杀)。问最好情况下,我方基地会受到多少点损
失。

Input

第一行两个数n,ATK,表示敌方人形兵器数量和我方人形兵器攻击力。
接下来n行,每行两个数A,Di,表示对方第i台人形兵器的攻击力和护甲值。
3<=n<=3×10^5,Ai,Di<=10^4,ATK<10^4

Output

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

Sample Input

3 7
30 8
7 35
1 209

Sample Output

28
【样例说明】
最好情况下,被秒杀的是敌方1、3号人形兵器,接下来需要5回合解决对方的2号人形兵器,对方共攻击4次,总计
造成28点伤害。可以证明没有更优的情况。

HINT

Source

[Submit][Status][Discuss]

HOME Back