Gangster Battles

Problem #192

Tags: hackercup puzzle

Who solved this?

This task is very similar to one given at Facebook Hackercup event in Jan 2015 (qualification, problem #2). We offer it to you so you can get better acquainted with problems of this popular contest and have greater motivation to participate in future years.

Several mighty gangster clans are discussing the next great battle between them. They agreed on the following terms:

Heads of the clans are now quite puzzled! Sides agreed to use P pistols and G grenades each. Every member of every clan then reported how many things he has - let us say that i-th member of the clan has p[i] pistols and g[i] grenades. And how then it is possible to pick members of the clan so that totals of their arsenal equal to required numbers?

They ask you to write a small program to help them. It is guaranteed that each clan have at least one subset of members satisfying the requirements. Of course if there are several choices, the one with more people should be preferred (because we do not like gangsters and want as many of them to be killed as possible).

Input data will contain N the number of clans in the first line, then values for P and G will follow.
Then all clans are described in N chunks of lines.
Each chunk has a single value K at its first line - total amount of members.
Then K lines will follow specifying p[i] and g[i] for a single member of this clan.
Answer should have N values - for every clan the maximum amount of its members who can participate.

Limits are: N <= 13, K <= 17, P <= 2000, G <= 3000.


input data:
3 1717 2058
455 634
414 774
371 377
436 557
513 753
803 496
401 809
508 731
854 556
666 521
274 987
910 418
249 1055
807 1640
225 230
501 503
410 427
381 570
610 755

3 2 4

Here from the first clan we pick members with 513, 803 and 401 pistols, from the second ones with 910 and 807, and from the third - all except that with 410.

You need to login to get test data and submit solution.