하모니

면접 대비

시간 제한2초메모리 제한1024 MB

요약

시간 N 안에서 훈련을 골라 에너지를 최대로 얻는 문제입니다. 조화의 합이 0이면 에너지가 두 배가 되며, 그 조화의 합과 에너지를 출력합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

한양이는 과거로 온 김에 숲속에 들어가 수련을 하려고 한다.

수련을 하나도 하지 않았을 때 한양이의 기력은 0이다. 또한 한양이는 궁궐로 다시 돌아가야 하므로, 수련에 투자할 수 있는 시간은 $N$ 으로 한정되어 있다!

한양이는 비급에 적힌 $T$ 개의 수련 중 서로 다른 수련들을 선택하여, 주어진 시간 내에서 최대의 기력을 얻고자 한다.

비급에 적힌 수련들은 각각 다음 항목을 가진다.

$M$ : 수련의 조화
$W$ : 수련 완료까지 걸리는 시간
$V$ : 수련 완료 시 얻을 수 있는 기력의 양

여기서 수련의 조화는 양(1) 또는 음(-1) 중 하나이다.

수련하러 가던 중, 한양이는 이 숲이 양과 음의 조화에 공명하는 특별한 숲이라는 사실을 주변 사람들을 통해 알게 된다!

숲에서 수련을 마쳤을 때 양과 음이 조화를 이루면, 즉 선택한 수련들의 조화( $M$ )의 합이 0이 되면 한양이가 얻은 기력( $V$ )의 합이 두 배가 된다. 한양이는 이를 고려해서 수련을 하려고 한다. 이런 한양이를 도와, 해야 할 수련을 골라 주어진 시간 내에 얻을 수 있는 최대의 기력을 구해보자.

입력

첫 번째 줄에 수련의 수 $T$ 와 수련할 수 있는 전체 시간 $N$ 이 주어진다. $(1 \le T \le 100;$ $1 \le N \le 1000)$

이후 $T$ 개의 줄에 걸쳐 $i$ 번째 수련의 조화 $M_i$ , 수련하는 데 걸리는 시간 $W_i$ , 수련 후 얻는 기력의 양 $V_i$ 가 주어진다. $(1 \le i \le T;$ $M_i = 1$ 또는 $M_i = -1;$ $1 \le W_i \le 300;$ $1 \le V_i \le 300)$

출력

첫 번째 줄에 기력이 최대일 때의 조화의 합과 그때의 기력을 출력한다. 가능한 출력값이 여러 개라면, 조화의 합의 절댓값이 작은 쪽의 조화의 합과 그때의 기력을 출력한다.

조화의 합의 절댓값까지 같다면, 조화의 합이 양수일 때의 값과 그때의 기력을 출력한다.

예제3

예제 1

입력

예상 출력

0 46

예제 2
입력
```
3 10
1 4 10
1 5 15
-1 6 1
```
예상 출력
```
2 25
```
예제 3
입력
```
3 3
1 1 5
-1 1 5
-1 3 20
```
예상 출력
```
0 20
```