Description

    新年快到了，集训队准备搞个聚会来庆祝下。经过大家的一番热烈讨论，决定去川王府吃火锅。
 
    有的人喜欢吃辣，有的人喜欢吃清淡的，为了让所有人都高高兴兴的，点的锅底自然得是鸳鸯锅底，至于配菜，则任由大伙点。
    川王府共有m道特色菜，为了大家能吃到更多的特色菜，队长规定每种特色菜不能超过3盘。同时，为了减少不必要的浪费，总盘数最多只能点n盘特色菜（点太多，大家也吃不完）。当然，大家为了吃的爽，会尽可能多的花队长的钱，但大家点的菜钱和锅底费的总和不会超过队长身上带的钱。因为队长付钱的时候，如果发现不够，就会叫大家付多出来的部分。

Input

输入包含多组数据
每组数据，第一行输入4个整数s(s<=100), m(1<=m<=25), n(n<=100), p (s<=p<=3000)。s表示锅底价格，m表示配菜的种类，n表示最多点n盘特色菜，p表示葱头帮主身上带的钱。
第二行输出m个整数，代表每一种特色菜的价格，价格都是整数且在[1,128]之间。 

Output

每组数据占一行，输出队长最多要付多少钱.

Sample Input

45 5 46 388
40 18 112 116 61 

Sample Output

388

HINT

Source

宁大第三届院赛