暂无测试数据。

$DD$ 要去摘果子了，她一开始的兴奋度是 $w$ 。她在一路上会经过 $n$ 个地点，每个地点有一棵果树或一个亭子，当经过一棵果树的时候，若当前 $DD$ 的兴奋度是 $x$，她的收获就是 $x*a_i$ ，但她的兴奋度会减少 $k\%$ ，当经过一个亭子的时候，她可以花费 $x*a_i$ 的收获来使自己的兴奋度增加 $c\%$ 。求她的最大收获是多少。

输入格式

第一行四个整数 $n,k,c,w$

接下来 $n$ 行，每行两个整数， $type_i$ 和 $a_i$ ，若 $type_i=1$ 该地为果树，若 $type_i=2$ 该地为亭子

输出格式

输出她的最大收获

数据范围

对于 $30\%$ 的数据， $n \leq 30$

对于另外 $20\%$ 的数据，$n \leq 1000, k=100$

对于 $100\%$ 的数据，$n \leq 10^5$, $0 \leq k,c,w,a_i \leq 100$，且保证最终答案不超过 $10^9$

5 50 50 10
1 10
1 20
2 10
2 20
1 30

375.00