화학 실험

n가지 종류의 화학 시약이 있고, 전체 M mg의 용액을 이 시약들에 모두 나누어 넣어야 한다.

시약 i에 x mg의 용액을 넣으면 a_i x + b_i mg의 어떤 가스가 발생한다. 각 시약에 넣는 용액의 양 x는 양의 정수여야 한다.

M mg의 용액을 n가지 시약에 나누어 넣어 모든 시약에서 같은 양의 가스가 발생하게 만들 수 있는지 판단하라. 가능하다면 각 시약에서 발생하는 같은 가스의 양을 출력하고, 불가능하다면 0을 출력한다.

첫째 줄에 시약의 종류 수 n이 주어진다. (1 <= n <= 100)

다음 n개의 줄에는 각 시약의 계수 a_i와 b_i가 공백으로 구분되어 주어진다. (1 <= a_i <= 100, 1 <= b_i <= 1000)

마지막 줄에는 전체 용액의 양 M이 주어진다. (1 <= M <= 10000)

모든 시약에서 같은 양의 가스가 발생하도록 용액을 나눌 수 있다면, 그 가스의 양을 첫째 줄에 출력한다.

그렇게 나눌 수 없다면 0을 출력한다.