만드는 중입니다

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

은행

시간 제한1초메모리 제한256 MB

요약
M개 지폐를 나누어 N명에게 각자 정해진 급여와 같은 금액을 줄 수 있는지 판단합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

어느 은행에 NN명이 급여를 받으러 왔다. ii번째 사람이 받을 금액은 aia_i 텡게다. 은행에 남은 지폐는 MM장이고, jj번째 지폐의 금액은 bjb_j 텡게다.

지폐는 쪼갤 수 없고, 한 장은 한 사람에게만 줄 수 있다. 모든 사람에게 각자의 급여와 정확히 같은 금액을 지폐로 지급할 수 있는지 판정하라. 쓰지 않고 남는 지폐가 있어도 된다.

입력

첫째 줄에 사람 수 NN과 지폐 수 MM이 주어진다 (1≤N≤151 \le N \le 15, 1≤M≤151 \le M \le 15).

둘째 줄에 급여 a1,a2,…,aNa_1, a_2, \dots, a_N이 주어진다 (1≤ai≤10001 \le a_i \le 1000).

셋째 줄에 지폐 금액 b1,b2,…,bMb_1, b_2, \dots, b_M이 주어진다 (1≤bj≤10001 \le b_j \le 1000).

출력

모든 사람에게 급여를 정확히 지급할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    1 5
    8
    4 2 5 1 3
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2 6
    9 10
    5 4 8 6 3 11
    
    예상 출력
    NO