시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 25 12 10 52.632%

문제

우리에게는 n가지 종류의 화학 시약이 있다.(이 시약을  t1,t2,...,tn이라고 하자.) 그리고 M mg의 용액이 있다. 이 용액 중 x mg을 시약 ti에 넣으면  aix+bi만큼의 어떤 가스가 발생한다고 한다.

우리가 할 일은 이렇다. M mg의 용액을 적절히 n가지 종류의 시약에 넣어서 각각의 시약에서 같은 양의 가스를 발생시키려 한다. 예를 들어  a1=3, b1=5, a2=4, b2=3, a3=1, b3=7 이라고 하자. 그리고 용액이 M = 27mg이라고 하자. 그러면 첫번째 시약에 6mg, 두번째 시약에 5mg, 세번째 시약에 16mg을 넣으면 세 개의 시약 모두 23mg이 발생하게 된다. 하지만 M=26일 경우에는 이렇게 세 개의 시약 모두 같은 양의 가스를 발생시키는 것이 불가능 하다.

시약의 개수 n과 용액의 양 M, 그리고 a1,a2,...,an과 b1,b2,...,bn이 주어져 있을 때, 만약에 n개의 시약 모두 같은 양의 가스를 발생 시킬 수 있으면 그 가스의 양을 출력하고, 그럴 수 없으면 0을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 시약의 종류 n(1<=n<=100)이 주어진다. 그리고 두 번째 줄부터 n+1번째 줄까지 공백을 사이에 두고 ai와bi가(1<=ai<=10, 1<=bi<=1000) 주어진다. (i+1번째 줄에 ai,bi 가 주어진다는 말이다.) 그리고 n+2번째 줄에는 용액의 양 M(1<=M<=10000) 이 주어진다.

출력

만약에 n개의 시약 모두 같은 양의 가스를 발생시키는 것이 가능하면 첫 번째 줄에 그 가스의 양을 출력하고, 그것이 불가능하면 첫째 줄에 대신 0을 출력하여라.

예제 입력

3
3 5
4 3
1 7
27

예제 출력

23

힌트