| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 60 | 30 | 24 | 51.064% |
한양이는 과거로 온 김에 숲속에 들어가 수련을 하려고 한다.
수련을 하나도 하지 않았을 때의 한양이의 기력은 0이다. 또한 한양이는 궁궐로 다시 돌아가야 하기에, 수련에 투자할 수 있는 시간이 $N$으로 한정되어 있다!
한양이는 비급에 적힌 $T$개의 수련 중 서로 다른 수련들을 선택하여, 주어진 시간 내에서 최대의 기력을 얻고자 한다.
이 비급에 적힌 수련들은 각각 아래 항목들을 가진다.
여기서 수련의 조화는 양(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)$
첫 번째 줄에 기력이 최대일 때의 조화의 양과 그때의 기력을 출력한다. 가능한 출력값이 여러 개라면, 조화의 절댓값이 작을 때의 조화의 양과 그때의 기력을 출력한다.
만약 조화의 절댓값까지 같다면, 조화가 양수일 때의 조화의 양과 그때의 기력을 출력한다.
5 20 1 5 10 -1 4 8 -1 9 7 1 5 15 1 15 8
0 46
두 번째, 네 번째 수련을 선택하여 총 기력 46이 가능합니다.
3 10 1 4 10 1 5 15 -1 6 1
2 25
첫 번째, 두 번째 수련을 골라 총 기력 25가 가능합니다.
첫 번째, 세 번째 수련을 고르면 총 기력 22로, 25보다 작아 선택하지 않습니다.
3 3 1 1 5 -1 1 5 -1 3 20
0 20