레이팅 미적용설명
농부 존과 소 떼가 프리스비 놀이를 하고 있다. 베시가 프리스비를 필드 저편으로 던졌는데, 상대 팀의 일꾼 마크에게 곧장 날아가고 있다! 마크의 키는 H이다 (1 <= H <= 1,000,000,000). 하지만 마크 주위에는 베시 팀의 소 N마리가 모여 있다 (2 <= N <= 20). 소들이 쌓아 올린 탑의 높이가 마크의 키 이상이 되어야만 프리스비를 잡을 수 있다. N마리의 소는 각각 키, 무게, 힘을 가진다. 소의 힘은 그 소의 위에 쌓일 수 있는 소들의 무게 총합의 최댓값을 나타낸다.
이러한 제약 아래에서, 베시는 자기 팀이 프리스비를 잡을 만큼 충분히 높은 탑을 쌓을 수 있는지, 가능하다면 그러한 탑의 최대 안전 계수가 얼마인지 알고 싶다. 탑의 안전 계수란 어떤 소의 힘도 초과하지 않으면서 탑의 맨 위에 추가로 올릴 수 있는 무게를 말한다.
제약
입력 형식
첫째 줄에 N과 H가 주어진다.
둘째 줄부터 1+N번째 줄까지 각 줄에 소 한 마리의 키, 무게, 힘이 주어진다. 모두 10억 이하의 양의 정수이다.
출력 형식
충분히 높은 탑을 쌓을 수 있다면 달성 가능한 최대 안전 계수를 출력한다. 그렇지 않으면 "Mark is too tall"을 (따옴표 없이) 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
guard.in · 출력을 쓸 파일 guard.out예제 1
입력
4 10
9 4 1
3 3 5
5 5 10
4 4 5출력
2문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Gold
태그