Valentine's Day '18 J5 & S2 - Ctudor's Cute Orchids

View as PDF

Submit solution

Points: 7
Time limit: 0.3s
Memory limit: 64M

Problem type

Ctudor (silent 'C') can't buy regular flowers because it's cruel to remove the reproductive organ of a plant for decorative purposes. Instead, he must buy orchids as those are interesting plants to grow. However, it is Valentine's Day and crappy grocery store orchids simply will not do, and Ctudor must buy good orchids from legendary plant collector Dennis. Dennis grows N types of orchids (numbered from 1 to N), and being a kind orchid collector offers M deals to buy the orchids. Each deal will have a cost C and can contain multiple of a certain type of orchid. Note that each deal can be used at most once.

Ctudor knows exactly which plants he wants and must determine the cheapest way to purchase them. Unfortunately, because his girl does not have enough lighting and plant space, Ctudor cannot buy extra orchids even if that lowers the cost.


1 \le N, N_i, C_i, M \le 10

0 \le D_i \le 100

0 \le Q_i \le 10

Input Specification

The first line will contain N and M, the number of orchid types and the number of deals offered.

The next N lines will contain C_i, the regular cost of orchid i.

The next M lines will contain N+1 integers. The first integer is D_i, the total cost of the deal and the next N integers are Q_i, the quantity of orchid i that are included in the deal.

The final line will contain N space-separated integers N_i, the i^\text{th} integer representing the quantity of orchid i that needs to be purchased.

Output Specification

The lowest possible cost to buy all the orchids.

Sample Input 1

2 2
5 3 0
10 1 2
3 2

Sample Output 1


Sample Input 2

3 2
4 1 1 0
9 2 2 1
1 2 1

Sample Output 2



There are no comments at the moment.