不论是泛舟中心湖，还是行船九州湖，都是无数西科大少年少女向往一件美事啊。

有一天，你喝着小酒，哼着小歌，走在天鹅湖岸边。这时，你惊奇地看到了，有一艘轻舟悄悄停泊在岸边。你心存犹疑，但是机会难得，你登上它，决定前往湖心一探究竟。湖中心是一片灿烂的花海，仿佛有吸引一般，你的轻舟自然而然地向那里靠近。拨开烂漫开放的野花，引入眼帘的是一个你从来没有见过的湖心岛。你缓步登临上岸，只见有一人在湖中亭子上面小憩，目似瞑，意暇甚(bushi)。

原来，在亭中小憩的是一位商人。这个商人在我们学校范围内的湖心亭摆摊。他告诉你，学校向他索取租金的方式不是租借摊位，而是根据他所卖的商品分别收取不同的收益。

这个商人有 件商品打算出售，并且给了它们初始定价列表 。他正要打算向学校缴纳租金，才发现学校已经设定了一个比例列表 ，但学校仍需要设定一个收费的基准金额 ，这意味着，对于第 件商品，学校将会收取费用 。

商人也是个不愿吃亏的主，因此对于某件商品，学校收取多少费用他就把商品售价提高多少。但是商人毕竟是商人，如果一个拥有 元的同学(购物者)来光临时，所能选择的购买方案数少于 种，商人就不愿在这摆摊了。因此学校也只能适可而止，请问： 学校设定的基准金额 可以取到的最大值是多少？

注：什么都不买也是一种购买方案。

第一行，三个整数  ，分别代表商人的商品件数，假定同学(购物者)所拥有的资金以及商人希望同学(购物者)至少拥有的购买方案数。

第二行，个整数，  ，代表商人给  件商品的最初定价。

第三行，个整数，  ，代表学校设定的不同物品的收费比例列表。

一个整数  ，代表学校所能设定的最大的收费基准金额。如果无论如何设定商人都不愿在此摆摊，那么  为  。

3 30 5
1 2 3
3 2 1

8

对于样例  ：当  时，三个物品的最终售价是： ，给定  元的情况下有以下购买方案：



达到了  种。

而  时，售价分别为： 。

则只有以下购买方案:



不足  种，因此答案为  。

1 1 2
1
1

0

1 1 2
2
1

0