CF739E Gosha is hunting

****共有 只神奇宝贝。 你有 个『宝贝球』和 个『超级球』。 『宝贝球』抓到第 只神奇宝贝的概率是 ，『超级球』抓到的概率则是 。

不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。

合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。

，时限 。

---

费用流可证凸性。

用 WQS 二分嵌套，第一层二分为每个『宝贝球』加权 ，第二个二分对每个『超级球』加权 。

然后甚至不需要 DP，每个神奇宝贝都是独立的，直接贪心即可。

对于每个神奇宝贝：

• 啥也不用：收益为

• 用『宝贝球』：收益为

• 用『超级球』：收益为

• 两个一起用：收益为

最后记录一下每种球各用了几个。

内层二分不看『宝贝球』的个数，而是调整 尽量让『超级球』个数接近 。

外层二分调整 然后根据内层二分使用的『宝贝球』来调整。

复杂度 。