만드는 중입니다

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

액체 분배

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

요약
섞인 병들을 옮겨 부어 각 연구소가 받을 A와 B의 양을 정확히 맞출 수 있는지 판정합니다.
난이도

어려움10점 중 8점

유형
기하, 그래프, 정렬
정답자
아직 제출이 없습니다

문제

우주 탐사를 여러 해 계속한 끝에 인류는 소행성에서 채취한 소량의 시료를 지구로 가져오는 데 성공했다. 시료는 액체 A와 액체 B가 완전히 섞인 혼합물이 담긴 여러 병에 나뉘어 있다.

탐사에 참여한 연구소들은 회수한 시료를 모두 나눠 받기로 합의했다. 각 연구소로 보낼 액체 A와 B의 양은 연구 주제에 따라 정해졌다.

그런데 이 결정 뒤에 현재 기술로는 혼합물에서 두 액체를 분리할 수 없다는 사실이 드러났다. 할 수 있는 작업은 한 병 이상에서 혼합물을 일정량 덜어 새 병에 함께 담는 것뿐이다.

합의된 분배가 실제로 가능한지 판단하라.

입력

입력은 다음 형식으로 주어지는 테스트 케이스 하나이다.

nn mm

a1a_1 ⋯\cdots ana_n

b1b_1 ⋯\cdots bnb_n

c1c_1 ⋯\cdots cnc_n

d1d_1 ⋯\cdots dnd_n

여기서 nn은 처음에 액체 A와 액체 B의 혼합물이 담긴 병의 개수이고, mm은 액체를 받을 연구소의 개수이다. nn과 mm은 모두 500 이하의 양의 정수이다. ii번째 병에는 액체 A가 aia_i mL, 액체 B가 bib_i mL 들어 있다. jj번째 연구소로 보낼 병에는 액체 A가 cjc_j mL, 액체 B가 djd_j mL 들어 있다. aia_i, bib_i, cjc_j, djd_j는 모두 10^6 이하의 양의 정수이다. ∑i=1nai=∑j=1mcj\sum_{i=1}^{n} a_i = \sum_{j=1}^{m} c_j이고 ∑i=1nbi=∑j=1mdj\sum_{i=1}^{n} b_i = \sum_{j=1}^{m} d_j이다.

출력

합의된 분배가 가능하면 Yes를, 그렇지 않으면 No를 한 줄에 출력한다.

힌트

첫 번째 테스트 케이스에서는 병 1에서 0.5 mL, 병 2에서 2.5 mL를 덜어 한 병에 모은 뒤 연구소 1에 보내는 방법만 조건에 맞다. 남은 액체를 담은 병은 연구소 2에 보낸다.

두 번째 테스트 케이스에서는 합의된 분배를 이행할 수 없다.

예제4

  1. 예제 1

    입력
    2 2
    1 3
    3 1
    2 2
    1 3
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    2 2
    2 2
    2 2
    1 3
    3 1
    
    예상 출력
    No
    
  3. 예제 3

    입력
    3 5
    2 5 8
    3 5 7
    3 3 3 3 3
    3 3 3 3 3
    
    예상 출력
    Yes
    
  4. 예제 4

    입력
    3 2
    4 4 4
    1 9 5
    6 6
    2 13
    
    예상 출력
    No