PANCAKES - Delicious Pancakes

no tags 

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.



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 106) 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 ri (from 1 to R). The input ends on a test-case having both N and R zero, which must not be processed.



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.



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



2 66

1 100


hide comments
Sayak Haldar: 2015-06-22 22:08:51

@Himanshu, bro, I know that feeling...caused me 2 was...:/

Akanksha Thareja: 2015-01-29 19:29:52

My code is giving correct output for all possible cases. but the spoj compiler is giving runtime (SIGSEGV) error. I am using arrays(1D and 2D) in my code, with no use of pointers. Please let me know due to what mistake does this error occur.

Last edit: 2015-01-29 20:04:32
pika_pika: 2013-07-04 10:49:46

the insufficient material and the stupid newline caused 2 WAs ... al last AC

Himanshu: 2013-06-14 18:36:43

easy but writing i insteed of j cost me 8 wrong answer.....i can't forgot this problem.....never..

Last edit: 2013-06-14 18:37:52
Aniket Kumar: 2013-06-05 13:23:41


piyush: 2013-06-03 16:31:53

long code but got ac in 1st attempt ... :)

Atul Kumar Verma: 2013-05-31 16:44:46

easy one AC in one Go..:)

Vyom sharma: 2012-06-18 09:52:49

whats the problem , i m getting 1 0 for the insufficient ingredients test case but its not getting accepted ??
anybody help plz

Aditya Muttur: 2011-12-25 12:03:43

@Wrong Answer: Thanks...Got it now.

Last edit: 2011-12-25 12:37:37
_|_: 2011-12-14 21:08:41

Do remember to multiply with 10 at first only otherwise at later it will give WA........took alot of time

Added by:Christian Kauth
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET