After the 2007 ICPC World Finals at Tokyo, Masao spent a couple of weeks visiting Japan, together with his nice teammates and his magnificent coach. In particular, they moved by train through the isles of Honshu and Kyushu. This problem is inspired by the many trains taken by the UPC teams during their travels around the world.

Consider a train with *m* cabins, each with room for 4 people.
Suppose that *n* groups of travellers, each with 1, 2, 3 or 4 members,
want to take the train.
There are three kinds of tickets, with increasing prices:
If a group travels split in several cabins,
each of its members pays *p*_{1}.
If a group travels together,
but with somebody else in the same cabin,
each of its members pays *p*_{2}.
If a group travels together and alone in a cabin,
each of its members pays *p*_{3}.

Given the price of every kind of ticket, the number of cabins, and the size of every group of travellers, can you maximize the benefit of the train company?

**Input**

Input consists of several cases.
Every case begins with three integer numbers:
the prices *p*_{1}, *p*_{2} and *p*_{3}.
Follows the number of cabins *m*,
the number of groups *n*,
and the size of each of these *n* groups,
all between 1 and 4.
Assume 1 ≤ *p*_{1} < *p*_{2} < *p*_{3} ≤ 10^{7},
1 ≤ *m* ≤ 12,
1 ≤ *n* ≤ 12,
and that there is always room for all the travellers in the train.

**Output**

For every case, print the maximum possible value of the tickets sold by the company. Note that every traveller must be accommodated in the train.

Public test cases

**Input**

2 3 4 3 4 1 2 3 4 1 10 100 4 6 3 3 3 3 2 2 1 3333 10000000 10 10 3 1 4 2 2 3 4 1 3 4

**Output**

37 133 270000000

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la UPC - Final
- Date
- 2010-09-22