시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB106019513318.169%

문제

신영이는 게임을 하는데 랙이 굉장히 심하게 걸려 화가 났다.

쾌적한 게임을 하기 위해선 일정량의 CPU 사용량과 메모리를 확보해야 한다.

신영이는 평소에 크롬 시크릿 탭을 굉장히 많이 켜두는데, 이 크롬 탭들을 지워서 자원을 확보하려 한다.

크롬 탭은 CPU 사용량, 메모리 사용량, 그리고 중요도로 나타낸다.

탭을 지울 경우 탭의 CPU와 메모리 사용량만큼 자원을 확보할 수 있다.

이때 탭들은 각각 중요한 정도인 중요도가 존재하고, 지운 탭들의 중요도의 합이 최대한 작도록 하고 싶다.

크롬 탭을 지워서 CPU와 메모리를 목표 이상 확보하려 할 때 중요도의 합의 최솟값을 구하여라.

입력

첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000)

은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. 은 목표 메모리 할당량이다.

다음 N 줄에는 다음과 같이 크롬 탭의 정보가 주어진다.

cpu, memory, priority (1 ≤ cpu ≤ M, 1 ≤ memory ≤ K, 1 ≤ priority ≤ 5)

출력

중요도 합의 최솟값을 출력한다.

만약 cpu와 메모리를 목표 만큼 확보할 수 없는 경우 -1을 출력한다.

예제 입력 1

4 8 3
4 1 1
4 2 2
7 1 2
7 3 3

예제 출력 1

3

출처

University > 경인지역 6개대학 연합 > shake! 2020 C번