현실적인 생일 축하 방안

시간 제한2.8초메모리 제한329 MB

요약
예산과 이름이 붙은 아이템 가격 목록이 주어질 때, 구매할 아이템들의 가격 합이 예산 이내인지 판정한다.
난이도

쉬움10점 중 2점

유형
해시맵, 구현, 배열
정답자
아직 제출이 없습니다

문제

루미의 28번째 생일의 날이 밝았다. 토카는 오래전부터 루미의 생일을 축하하고 싶었기 때문에 루미의 생일 선물을 구매하려 한다. 하지만 토카는 글러 먹은 소비 생활로 BB원밖에 가지고 있지 않았다.

어쩔 수 없이 토카는 루미에게 꼭 선물하고 싶었던 아이템 NN개 중 MM개를 구매해 선물하려 한다. 토카는 아이템 가격의 총합이 BB원을 초과하면 구매할 수 없다. 직접 아이템 가격의 합을 계산하기는 너무 힘들기 때문에 이를 확인하는 프로그램을 작성하기로 한다.

입력

첫 번째 줄에 토카의 보유 금액 BB, 아이템의 수 NN, 구매하려는 아이템의 수 MM가 공백으로 구분되어 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 토카가 가격을 알아본 아이템의 이름 ii와 가격 pp가 공백으로 구분되어 주어진다.

N+2N+2번째 줄부터 MM개의 줄에 걸쳐 NN개의 아이템 중 실제로 구매할 아이템의 이름 jj가 주어진다.

출력

토카가 가진 돈으로 토카가 사려는 아이템을 전부 구매하는 것이 가능하다면 acceptable, 불가능하다면 unacceptable을 출력하라.

제한

  • 0≤B≤10180\leq B\leq{10}^{18}
  • 1≤N≤2,8001\leq N\leq 2\\, 800
  • 1≤M≤min⁡(280,N)1\leq M\leq\min(280,N)
  • 0≤p≤10180\leq p\leq{10}^{18}, pp의 합은 2×10182\times{10}^{18}을 넘지 않는다.
  • i,ji, j는 알파벳 대소문자만으로 이루어진 11글자 이상 1515글자 이하의 문자열이다.
  •  ii는 중복되지 않는다.
  • jj는 토카가 가격을 알아본 아이템 중에서 중복 없이 주어진다.
  • 입력으로 주어지는 수는 모두 정수이다.

예제2

  1. 예제 1

    입력
    50 5 2
    Cake 35
    Clothes 30
    Toy 13
    Cartoon 3
    Goods 21
    Cake
    Toy
    
    예상 출력
    acceptable
    
  2. 예제 2

    입력
    50 5 2
    Cake 35
    Clothes 30
    Toy 13
    Cartoon 3
    Goods 21
    Cake
    Goods
    
    예상 출력
    unacceptable