自己口胡了一道题，大佬们看看怎么做。

---

有 $n$ 个商品，$m$ 张优惠券。每张优惠券只能对一件商品使用一次，但是可以不用。

每张优惠券有两个参数 $p,k$。如果第 $i$ 个商品的价格是 $a_i$，那么对这件商品使用参数为 $p,k$ 的优惠券可以使商品的价格变为 $a_i\times p\% + k$。那么请问如果想每件商品都买一个，至少要花多少钱。

比较特殊的是，$p$ 未必 小于 $100$，$k$ 未必 大于 $0$。

---

我出出来的时候觉得是贪心，后来发现是错的。问了同学，他说可以在 $n,m \leq 18$ 的时候状压DP。然后一问教练，说是费用流可以解决 $n,m \leq 1000$ 的情况。

所以我很好奇，这道题在可解的情况下 $n$ 最大可以去到多少。