Informatica Online Judge

  하냥의 영상만들기 [1922 / 0782]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : icp1481 - 0ms / 1209byte
My Best Submission (C++) : N/A

[koistudy.net (34th 신래훈)]
Writer ID : [gs16053]

Background

경곽 34기 최고의 동아리인 영상제작동아리 "하냥"의 기장 J는 오늘도 영상을 만들 궁리를 하며 하냥의 부원들을 불러모았다. 그러나 끝없는 영상 편집에 지칠 대로 지쳤던 J는 아이디어를 내는 것이 너무도 귀찮았던 나머지, 하냥의 부원들에게 일을 시키기로 마음먹는다.

성실하고 착한 하냥의 부원들은 J의 명령을 들어주기로 하고, 종이 한 장 당 한 개씩 아이디어를 적어내어, 총 $N$장의 종이를 파일철에 끼워 J에게 전달해준다. 사려깊은 부원들은 각 아이디어마다, 그 아이디어로 만들 수 있는 영상의 기대평점 $v$, 길이 $t$와, 제작 난이도 $d$를 같이 적어두었다.

하지만 아직도 귀찮음이 풀리지 않은 J는 부원들에게 어떤 영상을 만들지 스스로 고르라고 명령을 하며, 다음과 같이 까다로운 조건을 제시한다.

1. 하나 또는 그 이상의 아이디어를 선택하여 총 $T$분짜리의 영상을 만든다. 예를 들어, $T=5$ 일 때, 5분짜리 아이디어 하나를 선택해도 되고, 2분짜리 아이디어 하나와 3분짜리 아이디어 하나를 선택해도 된다.

2. 선택한 아이디어가 적힌 종이들은 모두 서로 이웃해있어야 한다. 즉, 파일철에 아이디어 $X_1$, $X_2$, $X_3$가 순서대로 끼워져 있을 때, $X_1$과 $X_2$를 같이 선택하는 것은 가능하다. 반대로 $X_1$과 $X_3$은 이웃하지 않기 때문에 $X_2$를 선택하지 않는 이상 둘을 동시에 선택할 수는 없다.

3. 두 개 이상의 아이디어를 선택했을 경우에 전체 영상의 재미가 한 영상으로만 몰리는 것을 방지하기 위해, 선택한 아이디어들의 기대평점을 비교했을 때 제일 높은 기대평점이 두 번째로 높은 기대평점의 두 배를 초과해서는 안 된다.

4. 제작 난이도가 $D$를 초과한 영상이 $L$개 이상 있으면 안 된다.

5. 최대한 적은 수의 아이디어를 선택해야 한다.

J는 이러한 조건에 맞춰 아이디어를 선택할 수 없으면 "영상을 아예 만들지 않겠다"고 으름장을 놓았고, J의 요구를 들은 부원들은 J의 인성에 감탄하며 혼란에 빠지고 말았다. 여러분의 뛰어난 코딩 실력을 이용하여 하냥이 영상의 기대평점을 최대한 높게 만들 수 있도록 도와주자.

Input

첫 번째 줄에 $N$, $T$, $D$, $L$이 입력된다.
다음 $N$줄에 걸쳐 파일철에 끼워진 순서대로 각 아이디어에 대한 정보가 주어지는데, 해당 아이디어로 만들 수 있는 영상의 기대평점 $v_i$, 길이 $t_i$, 제작 난이도 $d_i$가 공백을 사이에 두고 입력된다.

[입력값의 정의역]
$1≤N≤100,000$
$1≤T≤2,000,000$
$2≤D≤10$
$1≤L≤N$
$0≤v_{i}≤10,000$
$1≤t_{i}≤100$
$1≤d_{i}≤10$

Output

선택한 아이디어의 기대평점의 합의 최댓값과, 그 경우 선택한 아이디어의 수를 공백을 두고 출력한다.

IO Example

입력1
6 20 10 6
20 18 1
21 2 1
30 10 2
38 8 3
5 1 6
2 3 5

출력1
89 3

설명1
20분짜리 영상을 만들기 위해서는 1, 2번째 아이디어를 선택하거나, 2, 3, 4번째 아이디어를 선택해야 한다. 1, 2번째 아이디어를 선택하면 기대평점의 합이 41이지만, 2, 3, 4번째 아이디어를 선택하면 기대평점의 합이 89가 되므로 2, 3, 4번째 아이디어를 선택해야 한다.


입력2
5 20 10 5
516 10 2
536 8 3
1441 2 1
821 18 1
7 1 1

출력2
2262 2

설명2
20분짜리 영상을 만들기 위해서는 1, 2, 3번째 아이디어를 선택하거나, 3, 4번째 아이디어를 선택해야 한다. 그러나 1, 2, 3번째 아이디어를 선택할 경우, 제일 높은 기대평점은 1441으로, 두 번째로 높은 기대평점인 536의 두 배를 초과해버린다. 따라서 3, 4번째 아이디어를 선택해야 한다.


입력3
5 5 5 2
2 1 1
5 1 6
5 3 6
8 1 7
3 2 2

출력3
12 3

설명3
5분짜리 영상을 만들기 위해서는 1, 2, 3번째 아이디어를 선택하거나, 2, 3, 4번째 아이디어를 선택해야 한다. 그러나 2, 3, 4번째 아이디어를 선택할 경우 제작 난이도가 5를 초과하는 아이디어의 수가 3개로, 원래 제시된 조건인 2개를 초과했기 때문에 1, 2, 3번째 아이디어를 선택해야 한다.


입력4
4 20 10 5
139 6 2
160 10 4
217 4 5
299 16 3

출력4
516 2

설명4
20분짜리 영상을 만들기 위해서는 1, 2, 3번째 아이디어를 선택하거나, 3, 4번째 아이디어를 선택해야 한다. 두 경우 모두 기대평점의 합이 516으로 동일하나, 최대한 적은 수의 아이디어를 선택해야 하므로 3, 4번째 아이디어를 선택해야 한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]