继烟火表演和模拟赛 桥（IOI接线好像也能用凸函数做，虽然正解是前缀和优化dp）以外又一道分段凸函数题。
先固定勇士的攻击值atk，从小到大枚举，防御值为def
根据题意，当atk固定时，勇士损失的生命值为$max(0,atk[i]-def)*ceil(frac{hp[i]}{atk-def[i]})$
而勇士的生命值等于这个值+1，因为多的会被浪费掉。
实际上，这道题中有分数，可以想到整除分块。
根据整除分块的经验，如果hp[i]固定，$ceil(frac{hp[i]}{atk-def[i]})$的取值最多只有$sqrt{hp[i]}$种。
设从防御值从x-1->x，勇士会少损失的生命值函数为f(x)
实际上，每个怪物对于f(x)的影响是一个分段函数$max(0,atk[i]-x)*T$，其中T是战斗回合数。
这个函数在x<atk[i]的时候是个递减的一次函数，在x>=atk[i]的时候为直线y=0
由于加法对凸函数是封闭的，所以f(x)是一个凸函数。
如果atk增加，则每条直线第一段（递减的一次函数部分）的斜率都不会增加，所以随着atk增加，f(x)的值不增。同时f(x)-f(x-1)的值也不增。
实际上，当防御值+1（设为x+1）时费用会+=cd，但是会少花费f(x)-f(x-1)的钱用于购买生命值
所以当f(x)-f(x-1)<cd的时候应该停止增加防御值。
由于f(x)-f(x-1)的值在atk增加的时候不增，所以最优防御值在固定atk的时候是递减的，使用一个指针扫描即可。
凸函数使用差分维护。