SPOJ Problem Set (classical) 7405. Delicious Pancakes Problem code: PANCAKES

Just as promised, PolyProg will invite you to a bounteous pancake buffet right after this contest. Can you already feel the seductive odours dazing your senses? Well, before your mouth starts watering, you should solve this last problem.

As you might know, the basic ingredients to pancakes are flour, milk and eggs. These may be completed by a passel of additional toppings such as sugar, jam, berries, cheese, ham, mushrooms etc. As the chef of the evening was yet uncertain about the recipe he’d whip up tonight, he asked his assistant simply to buy random quantities of each ingredient.

With these quantities he could make N1 pancakes according to recipe 1, N2 if he decides to follow recipe 2, N3 for recipe 3 and so on and so forth. As the end of the competition is close, the chef will not have enough time to combine several recipes: All pancakes tonight will be of the same taste (too bad :( ). The repertoire of recipes is huge, and as we imagine you to have a ravenous appetite, you are to select the recipe that yields the largest number of pancakes.

 

INPUT

The input consists of several test-cases separated by an empty line. The first line of each test-case holds the number of ingredients N (1<=N<=50) the assistant bought followed by the number of recipes R (1<=R<=100) in the chef’s repertoire. Each of the next lines contains exactly N non-negative integers (no larger than 10⁶) informing about the ingredients. The first of these lines lists the quantities the assistant bought of each ingredient. The remaining R lines list the quantities (in the same order as the previous line) necessary to make ten pancakes according to the recipe r_i (from 1 to R). The input ends on a test-case having both N and R zero, which must not be processed.

 

OUTPUT

Your program should produce one line per test-case containing the recipe that yields the largest number of pancakes followed by the number of entire pancakes that can be made then. If there is a tie, prefer the recipe that appears first in the input.

 

SAMPLE INPUT

3 2

20 20 20

5 10 1

2 1 3

 

6 3

100 60 130 80 100 90

10 5 10 5 10 5

1 2 1 2 20 7

0 0 0 10 30 1

 

0 0

 

SAMPLE OUTPUT

2 66

1 100

 

---

Added by:	Christian Kauth
Date:	2010-09-26
Time limit:	1s
Source limit:	50000B
Languages:	All