samu-and-card-game-20

One day Samu went out for a walk in the park but there weren't any of her friends with her. So she decided to enjoy by her own. Samu noticed that she was walking in rectangular field of size N x M (units). So field can be divided into N horizontal rows, each containing M unit size squares. The squares have coordinates (X, Y) (1 ≤ X ≤ N , 1 ≤ Y ≤ M) ,  where X is the index of the row and y is the index of the column.

Samu is initially standing at (1, 1). Also she is having a deck of K cards. Cards have a number written on top and a number written on bottom too. These numbers tell the direction to move. It means if she is currently at some coordinate (X, Y) and value on top of card is A and on bottom of the card is B then she jumps to (X+A, Y+B).

Game is played with following rules :
1. She looks all cards in the order from 1 to K and consecutively chooses each card as the current one.
2.  After she had chosen a current card , she makes the maximally possible number of valid jumps with the chosen card.

She had been jumping for so long that she completely forgot how many jumps she had made. Help her count how many jumps she had made.

Input : 
The first line contains number of test cases T. The first input line of each test case contains two space separated integers N and M, the park dimensions.  The second  line  of each test case contains an integer K denoting the number of cards. Then follow K lines, each of them contains two integers A and B.

Output :
A single integer for each test case, The number of jumps Samu had made.  

Constraints : 
1 ≤ T ≤ 500
1 ≤ n, m ≤ 1000000000
1 ≤ K ≤ 10000
|A|,|B| ≤ 1000000000
|A|+|B| ≥ 1

SAMPLE INPUT
1
5 6
3
1 1
1 1
0 -4

SAMPLE OUTPUT
5

Explanation

Samu is initially positioned at square (1,1) and makes 4 steps by the first card (1,1). 
So, she jumps in following sequence (1,1) => (2,2) => (3,3) => (4,4) => (5,5) .
No more Jumps can be made with this card so now she discard this card and moves to next one.
Then she makes 0 jumps by the second card (1,1). 
She makes 1 more Jump by the third card (0,-4) and she ends up in square (5,1).
So she make 5 jumps in total.

Difficulty: EASY
Tags: Fundamentals

Implementation

Ad-hoc

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input())
while t>0:
	nm=str(input()).split()
	n=int(nm[0])
	m=int(nm[1])
	k=int(input())
	i=1
	x=1
	y=1
	jumps=0
	while i<=k:
		ab=str(input()).split()
		a=int(ab[0])
		b=int(ab[1])
		while True:
			if (x+a)>n or (y+b)>m or (x+a)<1 or (y+b)<1:
				break
			else:
				x=x+a
				y=y+b
				jumps=jumps+1
		i=i+1
	t=t-1
	print(jumps)
			


tc=int(input())
while tc:
	tc-=1
	N,M=list(map(int,input().split()))
	max_jump=0
	k=int(input())
	initial_x=1
	initial_y=1
	while k:
		k-=1
		x,y=list(map(int,input().split()))
		#while initial_x+x<=N and initial_y+y<=M and initial_x+x>=1 and initial_y+y>=1:
		while (1<=initial_x+x<=N and 1<=initial_y+y<=M):
			max_jump+=1
			initial_x+=x
			initial_y+=y
						
		

	print(max_jump)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

t = int(input());
while  t > 0 :
	lst = list(map(int,input().split(" ")));
	x= lst[0];
	y=lst[1];
	curx=1;
	cury=1;
	i = int(input());
	jump = 0;
	while i > 0:
		lst = list(map(int,input().split(" ")));
		tmpjump = 0;
		if(lst[0] > 0):
			tmpjump = (x- curx) // lst[0];
		elif( lst[0] < 0):
			tmpjump = (1- curx) // lst[0];
		
		if(lst[1] > 0):
			tmpjump = (y- cury) // lst[1] if lst[0] == 0 else min ((y- cury) // lst[1] , tmpjump);
		elif( lst[1] < 0):
			tmpjump = (1- cury) // lst[1] if lst[0] == 0 else min ((1- cury) // lst[1] , tmpjump);
		
		jump+=tmpjump;
		curx+= ( tmpjump * lst[0] );
		cury+= ( tmpjump * lst[1] );
		
		
		i-=1;
	print(jump);
	t-=1;


t           = eval(input())
for testCase in range(t):
	lastRow, lastCol    = list(map(int,input().split()))
	query       = eval(input())
	jumps       = 0

	firstRow,firstCol = 1,1
	currentRow, currentCol = 1,1

	for _ in range(query):
				a,b     = list(map(int,input().split()))
				x,y     = 0,0
				curJumpX,curJumpY = 0,0
				if a!=0:
					if a>0:
								curJumpX = (lastRow-currentRow)/a
					else:
								curJumpX = (firstRow-currentRow)/a
				if b!=0:
					if b>0:
								curJumpY = (lastCol-currentCol)/b
					else:
								curJumpY = (firstCol-currentCol)/b

				p = min(curJumpX,curJumpY)

				jumps+=p
				#print 'to jump',p
				currentRow += (p*a)
				currentCol += (p*b)

				if a==0:
								p = curJumpY
								#print 'to jump y',p
								jumps+=p
								currentCol += (p*b)
				if b==0:
								p = curJumpX
								#print 'to jump x',p
								jumps+=p
								currentRow += (p*a)

				#print currentRow,currentCol

	print(jumps)


test_cases=int(input())
t=1
while(t<=test_cases):
	stringarr=input()
	str=stringarr.split(" ")
	n=int(str[0])
	m=int(str[1])
	k=int(input())
	sum =0
	x=1
	y=1
	while(k>0):
		stringarr_2=input()
		str_2=stringarr_2.split(" ")
		A=int(str_2[0])
		B=int(str_2[1])
		if A>0:
			jumpA=(n-x)/A
		elif A==0:
			jumpA=9223372036854775807
		else:
			jumpA=(x-1)/-A
		if B>0:
			jumpB=(m-y)/B
		elif B==0:
			jumpB=9223372036854775807
		else:
			jumpB=(y-1)/-B
		if jumpA>jumpB:
			minvalue = jumpB
		else:
			minvalue = jumpA
		sum=sum+minvalue
		x=x+(minvalue*A)
		y=y+(minvalue*B)
		k=k-1
	print(sum)
	t=t+1


def moves(X, Y, cards):
	x, y = 0, 0
	moves = 0
	for i in cards:
		a, b = i
		x += a
		y += b
		while x < X and y < Y and x >= 0 and y >= 0:
			moves += 1
			x += a
			y += b
		x -= a
		y -= b
	return moves  


if __name__ == "__main__":
	t = int(input())

	output = []
	for _ in range(t):
		X, Y = [int(i) for i in input().split()]
		K = int(input())
		cards = []
		for _ in range(K):
			a, b = [int(i) for i in input().split()]
			cards.append((a, b))
		output.append(moves(X, Y, cards))

	for i in output:
		print(i)


def moves(X, Y, cards):
	x, y = 0, 0
	moves = 0
	for i in cards:
		a, b = i
		x += a
		y += b
		#print("---", X, Y)
		#print(x, y)
		while x < X and y < Y and x >= 0 and y >= 0:
			moves += 1
			x += a
			y += b
			#print(x, y)
		x -= a
		y -= b
	return moves  


if __name__ == "__main__":
	t = int(input())

	output = []
	for _ in range(t):
		X, Y = [int(i) for i in input().split()]
		K = int(input())
		cards = []
		for _ in range(K):
			a, b = [int(i) for i in input().split()]
			cards.append((a, b))
		output.append(moves(X, Y, cards))

	for i in output:
		print(i)


for i in range (int (input ())) :
	line = input().split(" ")
	n, m = int (line[0]), int (line[1])
	x = y = 1
	count = 0
	for j in range (int (input ())) :
		line = input().split(" ")
		a, b = int (line[0]), int (line[1])
		while 1 :
			x += a
			y += b
			if x <= n and x >= 1 and y <= m and y >= 1 :
				count += 1
			else :
				x -= a
				y -= b
				break
	print(count)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name

print 'Hello World!'
'''

t = int(input())
for i in range (t):
	n,m=list(map(int,input().split()))
	k=int(input())
	res=0
	x,y=1,1
	for j in range(k):
		a,b=list(map(int,input().split()))
		if a>0:
			xstep=(n-x)/a
		elif a==0:
			xstep=1000000001
		else:
			xstep=(x-1)/(-a)
			
		if b>0:
			ystep=(m-y)/b
		elif b==0:
			ystep=1000000001
		else:
			ystep=(y-1)/(-b)
			
		step=min(xstep,ystep)
		
		res=res+step
		
		x=x+(step*a)
		y=y+(step*b)
	print(res)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t= input()

t=int(t)
while(t>0):
	t=t-1
	X=1
	Y=1
	ct=0
	s=input()
	s=s.split()
	fx=int(s[0])
	fy=int(s[1])
	n=int(input())
	while n>0:
		n=n-1
		s=input()
		s=s.split()
		x=int(s[0])
		y=int(s[1])
		if  x>0:
			xs=abs((fx-X)/x)
		elif x<0:
			xs=abs((1-X)/x)
		else:			
			xs=1000000007
		if(y>0):
			ys=abs((fy-Y)/y)
		elif y<0:
			ys=abs((1-Y)/y)
		else:
			ys=1000000007
		c=min(xs,ys)
		
		X=X+(c*x)
		Y=Y+(c*y)
		ct=ct+c
		#print ct
	print(ct)
		


for i in range(eval(input())):
	line=list(map(int, input().split()))
	n,m=line[0],line[1]
	k=eval(input())
	ans=0
	p,s=1,1
	for j in range(k):
		l=list(map(int, input().split()))
		a,b=l[0],l[1]
		x,y=1000000007,1000000007
		#fx,fy=1,1
		if (a!=0):
			if (a>0):
				x=(n-p)/a
			else:
				x=(p-1)/abs(a)
				#fx=(-1)
		if (b!=0):
			if (b>0):
				y=(m-s)/b
			else:
				y=(s-1)/abs(b)
				#fy=(-1)
			
		z=min(x,y)
		ans+=abs(z)
		p=p+z*a
		s=s+z*b
	print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def get_max_elements_in_ap(start, end, step):
	return abs(int((end - start)/ step)) if step != 0 else -1


test_cases = int(input())
test_case_number = 0
while test_case_number < test_cases:
	n, m = list(map(int, input().split(' ')))
	k = int(input())
	A_B_values = []
	for i in range(k):
		A_B_values.append(list(map(int, input().split())))
		k -= 1
	curr_n, curr_m = 1, 1
	total_jumps = 0
	for i in A_B_values:
		a, b = i
		if a >= 0:
			end_a = n
		else:
			end_a = 1
		if b >= 0:
			end_b = m
		else:
			end_b = 1
		
		x_max = get_max_elements_in_ap(curr_n, end_a, a)
		y_max = get_max_elements_in_ap(curr_m, end_b, b)
		if x_max == -1:
			jumps = max(y_max, 0)
		elif y_max == -1:
			jumps = max(x_max, 0)
		else:
			jumps = min(x_max, y_max)
		curr_n = curr_n + jumps*a
		curr_m = curr_m + jumps*b
		# print curr_n, curr_m
		total_jumps += jumps
	print(total_jumps)
	test_case_number += 1

	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


t = int(input())

for _ in range(t):
	n, m = list(map(int, input().split()))
	k = int(input())
	curr_loc = [1, 1]
	jumps = 0
	for _ in range(k):
		card = list(map(int, input().split()))
		jump_loc = [None, None]
		jump_loc[0] =  curr_loc[0] + card[0]
		jump_loc[1] = curr_loc[1] + card[1]
		while jump_loc[0] >= 1 and jump_loc[0] <= n and jump_loc[1] >= 1 and jump_loc[1] <= m:

			curr_loc = jump_loc[:]
			jumps += 1
			jump_loc[0] =  curr_loc[0] + card[0]
			jump_loc[1] = curr_loc[1] + card[1]


	print(jumps)



t=int(input())
for i in range(t):
	n, m=list(map(int, input().split()))
	k=int(input())
	a, b=[], []
	jump=0
	x, y=1, 1
	for j in range(k):
		x1, y1=list(map(int, input().split()))
		#a.append(x1)
		#b.append(y1)
		while True:
			if x+x1>0 and x+x1<=n and y+y1>0 and y+y1<=m:
				jump+=1
				x=x+x1
				y=y+y1
				#print str(x)+", "+str(y)
			else:
				break
	print(jump)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def get_row_nums():
	return list(map(int, input().strip().split()))
	
	
testcases = int(input())

for each in range(testcases):
	row_lim, col_lim = get_row_nums()
	# total jumps taken so far
	jumps = 0
	row_pos = col_pos = 1
	
	total_cards = int(input())
	for each_card in range(total_cards):
		cards_nums = get_row_nums()
		
		# now check how many positions she can
		# jump with this card
		while row_pos > 0 and row_pos <= row_lim\
			and col_pos > 0 and col_pos <= col_lim:
			jumps += 1
			row_pos += cards_nums[0]
			col_pos += cards_nums[1]
			
		row_pos -= cards_nums[0]
		col_pos -= cards_nums[1]
		jumps -= 1
	print(jumps)


t = int(input())

while t>0:
	total_jumps = 0
	field_size = input()
	max_x, max_y = int(field_size.split(" ")[0]), int(field_size.split(" ")[1])
	min_x, min_y = 1,1
	curr_x, curr_y = 1,1
	k = int(input())

	while k>0:
		jump_width = input()
		jump_x, jump_y = int(jump_width.split(" ")[0]), int(jump_width.split(" ")[1])
		
		if jump_x < 0 :
			diff_in_x_dir = curr_x - 1
		else:
			diff_in_x_dir = max_x - curr_x

		if jump_x == 0:
			max_x_jump = 1000000001
		else:
			max_x_jump = diff_in_x_dir/abs(jump_x)

		
		if jump_y < 0 :
			diff_in_y_dir = curr_y - 1
                else:
                        diff_in_y_dir = max_y - curr_y

                if jump_y == 0:
                        max_y_jump = 1000000001
                else:
                        max_y_jump = diff_in_y_dir/abs(jump_y)


		jumps = min(max_x_jump, max_y_jump)
		total_jumps += jumps

		curr_x += jumps*jump_x
		curr_y += jumps*jump_y

		k-=1
	print(total_jumps)
	t-=1


tc = int(input())
for tt in range(tc):
	n,m = input().split(" ")
	n = int(n)
	m = int(m)
	length = n * m - 1
	prx = 1
	pry = 1
	q = int(input())
	jumps = 0
	for i in range(q):
		x,y = input().split(" ")
		x = int(x)
		y = int(y)
		now = 0
		if x >= 0 and y >= 0:
			if x == 0 and y != 0:
				now = (m-pry)/y
			elif y == 0 and x != 0:
				now = (n-prx)/x
			else:
				now = min((n-prx)/x, (m-pry)/y)
			jumps += now
			prx += now*x
			pry += now*y
		elif x >= 0 and y < 0:
			if x == 0 and y != 0:
				now = (pry-1)/abs(y)
			else:
				now = min((n-prx)/x, (pry-1)/abs(y))
			jumps += now
			prx += now*x
			pry += now*y
			
		elif x < 0 and y >= 0:
			if y == 0 and x != 0:
				now = (prx-1)/abs(x)
			else:
				now = min((prx-1)/abs(x), (m-pry)/y)
			jumps += now
			prx += now*x
			pry += now*y
		
		else:
			now = min((prx-1)/abs(x), (pry-1)/abs(y))
			jumps += now
			prx += now*x
			pry += now*y
			
		#print prx,pry,now,'--'

	print(jumps)


t = int(input())
while t>0:
	n,m = list(map(int,input().split()))
	k = int(input())
	i = 1
	j = 1
	ctr = 0
	steps = 0
	while ctr<k:
		x,y = list(map(int,input().split()))
		if x > 0:
			val1 = int((n - i)/x)
		elif x < 0:
			x = -x
			val1 = int((i-1)/x)
			x = -x
		else:
			val1 = 10000000000
		if y > 0:
			val2 = int((m - j)/y)
		elif y < 0:
			y = -y
			val2 = int((j-1)/y)
			y = -y
		else:
			val2 = 10000000000
		#print m,j
		min_val = min(val1,val2)
		if min_val == 10000000000:
			i = i
			j = j
		else:
			i = i + min_val*x
			j = j + min_val*y
			steps += min_val
		#print i,j
		ctr += 1
	print(steps)
	t -= 1
		
	


t=int(input());


#print list1;
for k in range(t):
	list1=[int(x) for x in ((input()).split())]
	M=list1[0]
	N=list1[1]
	

	K=int(input())
	
	List1=[]
	for i in range(K):
		list2= [int(x) for x in((input()).split())]
		List1.append(list2);
	
	
	
	x=1
	y=1
	count=0
	
	for j in range(K):
		while ((x<=M) and (y<=N)):
			if (((x+List1[j][0])<=M)and((y+List1[j][1])<=N) and ((x+List1[j][0])>=1) and ((y+List1[j][1])>=1)):
				x=x+List1[j][0]
				y=y+List1[j][1]
				count=count+1
				#print count
				#print x,y
				#print y
			
			
			
			else:
				break;
				
	print(count)
			
				
			
			
			
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for _ in range(int(input())):
	n,m = list(map(int,input().split()))
	jumps = 0
	cur = [1,1]
	for k in range(int(input())):
		a,b = list(map(int,input().split()))
		pa = max(n,m)+1
		pb = pa
		if a>0:
			pa = (n-cur[0])/a
		elif a<0:
			pa = (1-cur[0])/a
		if b>0:
			pb = (m-cur[1])/b
		elif b<0:
			pb = (1-cur[1])/b
		
		jump = min(pa,pb)
		jumps = jumps+jump
		cur[0] = cur[0] + jump*a
		cur[1] = cur[1] + jump*b
	print(jumps)


t = int(input())
for i in range(t) :
	line = str(input()).split(' ')
	n = int(line[0])
	m = int(line[1])
	k = int(input())
	#print n,m,k
	sx = 0
	sy = 0
	cnt = 0
	for j in range(k) :
		line = str(input()).split(' ')
		a = int(line[0])
		b = int(line[1])
		xc = 0
		yc = 0
		flaga = False
		flagb = False
		if a < 0 :
			xc = sx/abs(a)
		elif a > 0 :
			xc = (n-1-sx)/a
		else  :
			flaga = True
		if b < 0 :
			yc = sy/abs(b)
		elif b > 0 :
			yc = (m-1-sy)/b
		else :
			flagb = True
		steps = 0
		if flaga :
			steps = yc
		elif flagb :
			steps = xc
		elif xc < yc :
			steps = xc
		else :
			steps = yc	
		sx = sx+steps*a
		sy = sy+steps*b
		cnt = cnt+steps
	print(cnt)
			


t=int(input())
for i in range(t):
	inp=input().split()
	n=int(inp[0])
	m=int(inp[1])
	k=int(input())
	prev_x=1
	prev_y=1
	ans=0
	for j in range(k):
		inp=input().split()
		a=int(inp[0])
		b=int(inp[1])
		if a<0:
			sx=(prev_x-1)//abs(a)
		elif a>0:
			sx=(n-prev_x)//abs(a)

		if b<0:
			sy=(prev_y-1)//abs(b)
		elif b>0:
			sy=(m-prev_y)//abs(b)
		
		if a==0 and b!=0:
			sx=sy
		elif b==0 and a!=0:
			sy=sx
		
		if sx<=sy:
			step=sx
		else:
			step=sy
		prev_x+=step*a
		prev_y+=step*b
		ans+=step
	print(ans)


import sys
for x in range(0,eval(input())):
	n,m= list(map(int,sys.stdin.readline().split()))
	i=1
	j=1
	ans=0
	for k in range(0,eval(input())):
		a,b= list(map(int,sys.stdin.readline().split()))
		ca=0
		cb=0
		c=0
		jmpa=0
		jmpb=0
		if(a==0 and b==0):
			continue
		if(a<0):
			ca= i-1
		else:
			ca=n-i
			
		if(b<0):
			cb= j-1
		else:
			cb= m-j
		#print 'ca,cb=', ca,cb
		
		if(a==0):
			jmpb= cb/abs(b)
			c=jmpb
			j=j+c*b
		elif(b==0):
			jmpa= ca/abs(a)
			c=jmpa
			i=i+c*a
		else:
			#print 'inside'
			jmpb=cb/abs(b)
			jmpa=ca/abs(a)
			c= min( abs(jmpa),abs(jmpb))
			i= i+ c*a
			j=j+ c*b
		
		#print 'cnt=',c
		ans+=c
		#print "i,j=",i,j
	print(ans)
		
			
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
test_cases = int(input())
def is_safe_move(x, y, row, col):
	if x >= 1 and row >= x and y >= 1 and col >= y:
		return True
	else:
		return False
		
def park_count(card_list, row, col):
	count = 0
	next_x = 1
	next_y = 1
	if row == 0 and col == 0:
		return 0
	for card in card_list:
		A = int(card[0])
		B = int(card[1])
		while (True):
			next_x = next_x + A
			next_y = next_y + B
			if is_safe_move(next_x, next_y, row, col):
				count = count + 1
			else:
				next_x = next_x - A
				next_y = next_y - B
				break
	
	return count 
	
	
for i in range(test_cases):
	count = 0
	row_and_col = input().split(' ')
	row,col = int(row_and_col[0]), int(row_and_col[1])
	no_of_cards = int(input())
	card_list = []

	for card in range(no_of_cards):
		card_list.append(input().split(' '))
	
		
	print(park_count(card_list, row, col))