# Cabin optimization P23968

Statement

thehtml

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 p1. If a group travels together, but with somebody else in the same cabin, each of its members pays p2. If a group travels together and alone in a cabin, each of its members pays ‍p3.

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 p1, p2 and p3. 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 ≤ p1 < p2 < p3 ≤ 107, 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++