Cabin optimization P23968


pdf   zip


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 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.


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


  • Information
    Salvador Roura
    Official solutions
    User solutions