Healthy Holsteins

Time limit1sMemory limit1024 MB

Summary

Given vitamin requirements and feed contents, find the fewest distinct feed scoops that meet every vitamin minimum, and print which feeds to use.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

Farmer John takes pride in having the healthiest dairy cows in the world. He knows the vitamin content of one scoop of each feed type and the minimum daily vitamin requirement for the cows. Your goal is to feed the cows so they stay healthy while minimizing the number of feed scoops given to each cow. Given the daily requirement for each vitamin, find the smallest combination of feed scoops that meets at least the minimum requirement for every vitamin. Vitamins are measured in integer units. A cow can be fed at most one scoop of any feed type. A solution is guaranteed to exist for all input data.

Input

The first line contains an integer $V$ ( $1 \le V \le 25$ ), the number of vitamin types. The second line contains $V$ integers ( $1 \le$ each value $\le 1000$ ), the minimum daily requirement for each vitamin. The third line contains an integer $G$ ( $1 \le G \le 15$ ), the number of feed types. The next $G$ lines each contain $V$ integers ( $0 \le$ each value $\le 1000$ ), giving the amount of each vitamin in one scoop of that feed. The first of these lines describes feed 1, the second describes feed 2, and so on.

Output

Print one line containing the minimum number of scoops a cow must eat, followed by the feed types given to the cow in sorted order from smallest to largest.

Examples1

Example 1

Input

4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399

Expected output

2 1 3