문제
지난주에 문제를 고르는 알고리즘을 고안해냈던 정쌤은 알고리즘의 그닥 효율적인 방법으로 문제를 고르지 못한다고 생각하고 새로이 문제를 고르는 방법을 만들려고 한다.
각 문제들에 대해 3개의 변수 MT, CT, V가 정해지는데 MT는 문제의 데이터 만드는데 걸리는 시간을 뜻하는 정수(1≤MT≤100), CT는 학생이 문제를 푸는데 걸리는 시간을 뜻하는 정수이고(1≤CT≤100), 마지막으로 V는 학생들의 문제에 대한 만족도(1≤V≤100)를 뜻한다. 만족도는 높을수록 좋다.
정쌤은 한 문제씩 작업을 하기 때문에 선택된 문제의 MT들의 합만큼의 데이터를 만드는 시간을 필요로 하며, 학생들은 선택된 문제의 CT의 합 만큼의 시간을 소요하여 문제를 풀게 된다. 그리고 선택된 문제들에 대한 만족도는 V들의 합이 된다.
정쌤은 선택할 문제의 수 N과 SMT와 SCT가 주어졌을 때, 선택된 문제의 MT의 합이 SMT이하이고, CT의 합이 SCT이하일 때, 만족도 V들의 합이 최대가 되게 문제를 내어 학생들의 모의고사에 대한 열의를 높이고자 한다. 하지만 최근 들어 연구실 일이 바쁜 정쌤은 열심히 공부하는 당신에게 프로그래밍을 구현하는 것을 요청하였다. 정쌤의 요청을 들어주자.
입력형식
입력
입력의 첫번째 줄에는 M, N과 SMT, SCT가 주어진다. 여기서 M은 정쌤이 가지고 있는 문제의 수를 뜻한다(N≤M, M≤50, 1≤SMT, SCT≤100).
그 다음 줄부터 M개의 줄에는 문제들에 대한 정보가 세 개의 숫자로 한 줄에 하나씩 입력되는데 각각 MT CT V를 뜻한다.
출력
조건을 만족하여 문제를 냈을 때 V의 합이 최대가 될 경우를 출력한다.
예제
5 2 10 10
1 2 3
2 3 4
3 4 5
5 6 7
7 8 9
12
로그인해야 코드를 작성할 수 있어요.