经营与开发
题目描述
$4X$ 概念体系,是指在 PC 战略游戏中一种相当普及和成熟的系统概念,得名自 $4$ 个同样以 EX 为开头的英语单词。
- $\verb!eXplore!$(探索)
- $\verb!eXpand!$(拓张与发展)
- $\verb!eXploit!$(经营与开发)
- $\verb!eXterminate!$(征服)
——维基百科
今次我们着重考虑 exploit 部分,并将其模型简化:
你驾驶着一台带有钻头(初始能力值 $w$)的飞船,按既定路线依次飞过 $n$ 个星球。星球笼统的分为 $2$ 类:资源型和维修型。($p$ 为钻头当前能力值)
1. 资源型:含矿物质量 $a_i$,若选择开采,则得到 $a_i\times p$ 的金钱,之后钻头损耗 $k\%$,即 $p\gets p\times (1-0.01k)$;
2. 维修型:维护费用 $b_i$,若选择维修,则支付 $b_i\times p$ 的金钱,之后钻头修复 $c\%$,即 $p\gets p\times (1+0.01c)$。
注:维修后钻头的能力值可以超过初始值(你可以认为是翻修 + 升级)
金钱可以透支。
请作为舰长的你仔细抉择以最大化收入。
输入输出格式
输入格式
第一行 $4$ 个整数 $n,k,c,w$。
以下 $n$ 行,每行 $2$ 个整数 $\mathrm{type},x$。
- $\mathrm{type}$ 为 $1$ 则代表其为资源型星球,$x$ 为其矿物质含量 $a_i$;
- $\mathrm{type}$ 为 $2$ 则代表其为维修型星球,$x$ 为其维护费用 $b_i$;
输出格式
一个实数(保留 $2$ 位小数),表示最大的收入。
输入输出样例
输入样例 #1
5 50 50 10
1 10
1 20
2 10
2 20
1 30
输出样例 #1
375.00
说明
### 数据范围及约定
- 对于 $30\%$ 的数据 $n \le 100$;
- 另有 $20\%$ 的数据 $n \le 1000$,$k=100$;
- 对于 $100\%$ 的数据 $n \le 100000$,$0 \le k,c,w,a_i,b_i \le 100$,保证答案不超过 $10^9$。