Cabin optimization P23968

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

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₁, p₂ and p₃. 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₁ < p₂ < p₃ ≤ 10⁷, 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.