만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

배부른 게임

면접 대비

시간 제한2초메모리 제한1024 MB

요약
네 개의 나머지 조건 x ≡ r_i (mod d_i)를 모두 만족하는 가장 작은 음이 아닌 정수 x를 구합니다.
난이도

보통10점 중 4점

유형
정수론, 수학
정답자
아직 제출이 없습니다

문제

최근 판엠의 주민들 사이에서 '배부른 게임'이 인기를 끌고 있다. 규칙은 다음과 같다. 게임을 시작할 때 양의 정수 d1d_1, d2d_2, d3d_3, d4d_4가 공개된다. 이어서 플레이어에게 정수 r1r_1, r2r_2, r3r_3, r4r_4가 제시된다. 모든 1≤i≤41 \le i \le 4에 대해 x≡ri(moddi)x \equiv r_i \pmod{d_i}를 만족하는 가장 작은 수 xx를 먼저 외치는 플레이어가 이긴다. xx를 최대한 빨리 계산하는 프로그램을 작성하라.

입력

첫 줄에 네 양의 정수 d1d_1, d2d_2, d3d_3, d4d_4 (1≤di≤5001 \le d_i \le 500)가 주어진다.

둘째 줄에 네 정수 r1r_1, r2r_2, r3r_3, r4r_4 (0≤ri<di0 \le r_i < d_i)가 주어진다.

답이 항상 존재함이 보장된다.

출력

위 조건을 만족하는 가장 작은 수 xx를 출력한다.

예제1

  1. 예제 1

    입력
    7 12 5 2
    3 8 4 0
    
    예상 출력
    164