화학 실험
면접 대비시간 제한2초메모리 제한128 MB
용액 M mg을 각 시약에 양의 정수로 나누어 넣었을 때 모든 시약에서 a_i*x+b_i 값이 같아지도록 분배할 수 있는지 판별하고 가능하면 그 값을, 아니면 0을 출력합니다.
문제
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을 출력한다.