시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB137474342.157%

문제

우리에게는 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 ≤ 100, 1 ≤ bi ≤ 1000) 주어진다. 그리고 n+2번째 줄에는 용액의 양 M(1 ≤ M ≤ 10000) 이 주어진다.

출력

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

예제 입력 1

3
3 5
4 3
1 7
27

예제 출력 1

23

예제 입력 2

3
3 5
4 3
1 7
26

예제 출력 2

0

출처