#1985 포만감

23  1 s   128 MB  

Description

 

매번 소개팅에서 fail하는 paian. 하지만 그는 다시 한번 소개팅을 받았고 이번 소개팅은 어디서 할까 장소를 물색하던 중 그간 소개팅으로 인해 자신이 거지라는 것을 깨닫게 된다.
남자 paian은 들어오는 소개팅을 절대 거절하지 않는다. (가끔 거절 할 때도 있다고 생각되는 건 당신의 기분 탓.)
소개팅 장소의 후보를 결정한 그는 그 장소의 메뉴가 내가 원하는 포만감을 충족시켜줄 수 있는지 알고 싶다. 그리고 만약 가능하다면 최저가격은 얼마인지도 알고 싶어 당신에게 물어
보았다.
이 포만감을 만족 시킬 수 있는지 판단하고 가능하다면 “YES”와 최저 가격을 출력하여라.
만약 포만감을 만족 시킬 수 없다면 “NO”를 출력한다.

Input

 

테스트 케이스 t가 주어진다.
그리고 각 테스트 케이스 마다 아래의 정보가 주어진다.
p(포만감 0 < p < 10000) n (음식의 개수) (0 < n < 1000)
name_1(음식 이름,문자열) p_1(음식이 채워주는 포만감) m_1(음식의 가격)
name_2(음식 이름,문자열) p_2(음식이 채워주는 포만감) m_2(음식의 가격)
.
.
name_n(음식 이름,문자열) p_n(음식이 채워주는 포만감) m_n(음식의 가격)
(0 < p_i< 10000) (0 < m_i < 100000)

Output

testcase마다 “YES” 혹은 “NO”를 출력하고 만약 “YES”일 경우 옆에 최저 가격도 출력한다.

Sample Input

Sample Output

3
10
3
Aa 3 5
Bb 10 50
Cc 1 27
18
3
apple 6 6
steak 16 13
noodle 9 23
10
2
abc 3 53
ABC 8 123
YES 42
YES 18
NO

Source

2012 Ajou Programming Contest, Division 1