#1990 대출은 솔로몬

18  1 s   128 MB  

Description

 

어젯밤 11학번 '줏응규'는 우울함에 사로잡혀 친구들을 불러내어 '맥주할인'에서 친구들과 술을 마셨다. '줏응규'가 소집하였지만 그에겐 치명적인 약점이 있었는데, 주량이 소주 한잔, 맥주 한 병이였던 것. 이번에는 먼저 취하지 않겠다는 굳은 약속을 믿은 그의 친구들은 그의 소집에 응하였고, 대신 내기를 걸었다. '줏응규'가 가장 먼저 취하면, 술값은 그가 지불하고 다음 날 모두 A교시 수업을 대리출석을 해주기로 한 것.
그리고 그는 졌다.
주량이 워낙 적어 숙취 따윈 없는 그는 우울한 마음과 지갑을 안고 학교로 출발하였다. 수업 전에 도착하였지만, 교수님께서도 곧 도착할 상황. 교수님이 도착하시기 전에, 친구들의 대리출석을 최대한 많이 완료해줘야 한다. 하지만 이도 그리 만만한 일이 아니다. 그의 절친한 친구(?) 인 '조철' 같은 친구들은 자신의 대리출석도 안되었는데 다른 친구들 것을 해주면 차마 입에 담지 못할
말들을 내뱉어 낸다. 그런 말을 들으며 다른 친구들을 챙겨주느니, 그는 일단 그런 부류의 친구들부터 챙겨주기로 했다.
또 조금 복잡하게도, '줏응규'의 친구들 중 어떤 친구는 학번을 외우고 있거나 패턴이 입력하기 매 우 쉬워 금방 끝나지만, 또 다른 친구들은 그렇지 못하다.
우리의 친구 '줏응규'가 대리출석 해줄 수 있는 최대한의 수를 구해보자.

Input

 

첫 줄엔 테스트 케이스 n이 주어진다. (1 ≤ n ≤ 100)
테스트케이스마다 아래의 정보가 주어진다.
대리출석을 원하는 사람 수 m, 제한 시간 t이 각 테스트 케이스의 1번 째 줄에 입력된다.
(1 ≤ m ≤ 100, 1 ≤ t ≤ 300. n, m, t 는 모두 정수)
2~(m+1)번째 줄에는 각각 두 개의 정수 r, p가 들어온다.
n
m t
r1 p1
r2 p2
…..
rm pm
r은 1 ≤ r ≤ 30 범위내의 정수로서, 대리출석 시 필요한 소모시간을 나타낸다.
p는 0혹은 1이 입력된다. 1은 해당 라인의 학생은 우선순위를 가짐을 의미한다.
우선순위를 가진 학생은 가지지 않은 학생들보다 무조건 먼저 대리출석 처리해줘야만 한다.

Output

해당시간까지 대리출석이 완료된 최대 사람 수를 각각 n개의 줄에 결과값으로 출력한다.

Sample Input

Sample Output

2
5 28
3 0
18 1
5 0
6 0
10 0
10 30
20 1
1 0
2 1
2 0
7 0
13 0
3 0
4 0
5 1
5 0
3
5

Source

2012 Ajou Programming Contest, Division 2