Pizza
(Main file name: pizza)

The problem arises in the University College Cork student dorms. There is a large order of pizzas for a party, and many of the students have vouchers for acquiring discounts in purchasing pizzas. A voucher is a pair of numbers e.g. (2,4), which means if you pay for 2 pizzas then you can obtain for free up to 4 pizzas as long as they each cost no more than the cheapest of the 2 pizzas you paid for. Similarly a voucher (3,2) means that if you pay for 3 pizzas you can get up to 2 pizzas for free as long as they each cost no more than the cheapest of the 3 pizzas you paid for. The aim is to obtain all the ordered pizzas for the least possible cost. Note that not all vouchers need to be used, and a voucher does not need to be totally used.

Input Formats

An input file for LP systems contains the following facts:
An input file for MiniZinc defines the following constants:

Output format

The output should contain exactly one fact of the form cost(K), where K is the minimum cost required to obtain the pizzas.

Samples


LP InputMinizinc InputOutput
n_pizzas(4).
pizza(1,10).
pizza(2,5).
pizza(3,20).
pizza(4,15).
n_vouchers(2).
voucher(1,1,1).
voucher(2,2,1).

n = 4;
price = [10,5,20,15];
m = 2;
buy = [1,2];
free = [1,1];
cost(35).
n_pizzas(4).
pizza(1,10).
pizza(2,15).
pizza(3,20).
pizza(4,15).
n_vouchers(7).
voucher(1,1,1).
voucher(2,2,1).
voucher(3,2,2).
voucher(4,8,9).
voucher(5,3,1).
voucher(6,1,0).
voucher(7,4,1).

n = 4;
price = [10,15,20,15];
m = 7;
buy = [1,2,2,8,3,1,4];
free = [1,1,2,9,1,0,1];

cost(35).
n_pizzas(10).
pizza(1,70).
pizza(2,10).
pizza(3,60).
pizza(4,60).
pizza(5,30).
pizza(6,100).
pizza(7,60).
pizza(8,40).
pizza(9,60).
pizza(10,20).
n_vouchers(4).
voucher(1,1,1).
voucher(2,2,1).
voucher(3,1,1).
voucher(4,1,0).
n = 10;
price = [70,10,60,60,30,100,60,40,60,20];
m = 4;
buy = [1,2,1,1];
free = [1,1,1,0];
cost(340).
1