SP33324 ADASALE - Ada and Salesman

Ada住在Bugladesh。这是一个非常特别的国家：它有一些城市，但由于政府不会“浪费”金钱，因此它们全都位于一条简单的道路上。 Ada担任着旅行推销员。她在城市之间旅行，同时买卖产品。产品在每个城市的价格都有所不同（稍后说明）。Ada会骑自行车旅行（避免支付旅行费用），因此她一次最多可以在背包中携带K个物品。 她现在想从城市1到城市n,并以最大化利润的方式购买/出售商品。你能帮帮她吗？ 规则如下: Ada有一个最多可以容纳K个物品的背包。她会径直向前旅行（从城市C到城市C + 1）。如果她在城市c中，则可以立即搬到下一个城市，也可以购买许可证以交易Lc的钱。对于每个城市，它被赋予了一个神奇常数Pc。购买/销售系统很奇怪。在城市c中购买商品时，如果已经将i-1个物品放在了背包中，将会花费Pc * i * c％MOD。类似地，在城市c中出售某项物品时，如背包中的物品已有i个，会获得Pc * i * c％MOD。您可以在城市中购买任意数量的商品，也可以在城市中销售任意数量的商品。但无论如何都不能超过K（并且显然不能为负）。

输入的第一行将包含三个整数1 ≤ N, K ≤ 3000 和1 ≤ MOD ≤ 10^4。 下一行将包含N个整数 0 < Li ≤ 1000,，每个城市的许可成本。 下一行将包含N个整数0 < Pi ≤ 1000，每个城市的魔法常数。

输出Ada可以获得的最大金额。