시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 64 7 6 37.500%

문제

KTX(Korea Train eXpress)는 KORAIL이 운영하는 대한민국 고속철도이며, 서울과 주요 도시를 연결한다. KTX-산천은 대한민국의 독자적인 기술로 개발된 열차로 350km/h까지 속도를 높일 수 있다. 현재 속도를 최고 400km/h까지 올릴 수 있는 다음 열차를 연구 개발중이다.

고양차량사업소는 한국에서 가장 큰 차량기지로, KTX 열차의 입출고 관리와 검수를 담당한다.

고양차량사업소에서 출발한 열차는 자정 전에 기지로 돌아오며, 아침에 떠나게 된다. 열차는 기지의 동쪽이나 서쪽으로 들어오며, 나갈때도 동쪽이나 서쪽을 이용한다. 각 차량이 들어오는 곳이나 나가는 곳은 모두 정해져 있다. 또, 출발시간과 도착시간도 모두 정해져 있다. 즉 각 열차가 기지 내에 있는 시간 구간 [t1, t2]와, 나가고 들어오는 방향 d1, d2를 이용해 나타낼 수 있다. [-6E, 13W]는 시간 -6에 동쪽으로 기지에 들어오고, 시간 13에 서쪽으로 기지를 나가는 열차라는 뜻이다. 그 시간에는 기지 내의 평행 선로에서 대기하고 있는다.

두 열차가 동시에 같은 방향으로 기지를 떠나거나 들어오는 것은 불가능하다. 모든 열차에는 다른 열차에 방해받지 않고 출발할 수 있도록 선로가 할당된다. 아 그림 1은 열차[-2E,2W]가 열차 [-1W,4W]에 의해 막혀있기 때문에 불가능한 경우이다. 그림 2(a)와 2(b)는 모두 가능한 경우이다. 2(b)는 선로를 최소 개수로 사용한다.

그림 1. 불가능한 선로 할당

그림 2. 가능한 선로 할당

KORAIL 연구소장 Dr. 좌는 고양차량사업소에서 보관하는 열차의 수를 늘리려고 한다. Dr. 좌는 선로의 개수가 고정되어 있기 때문에, 차량을 보관하는 일이 매우 어려워 질 것이라고 예견했다. 선로의 길이는 모든 열차를 보관할 수 있을 정도로 매우 길다. Dr. 좌는 모든 열차가 다른 열차에 막히지 않고 정시에 출발하고 도착할 수 있게 하기 위해 필요한 선로의 최소 개수를 구하려고 한다. Dr. 좌를 도울 수 있는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 열차의 수 n (1 ≤ n ≤ 10000)이 주어진다. 다음 n개 줄에는 열차를 나타내는 t1d1t2d2가 주어진다. t1과 t2는 정수이고 -1,000,000 ≤ t1 < 0 < t2 ≤ 1,000,000, d1,d2 ∈ {E, W} 를 만족한다.

출력

첫째 줄에 필요한 선로 개수의 최소값을 출력한다.

예제 입력 1

3
4
-4E1W
-3E3E
-1W4W
-2E2W
3
-3E9W
-2E8W
-1E7W
3
-3E9E
-2W8W
-1W7W

예제 출력 1

2
3
1
W3sicHJvYmxlbV9pZCI6Ijg5MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJLVFggXHVjNWY0XHVjYzI4IFx1YWUzMFx1YzljMCIsImRlc2NyaXB0aW9uIjoiPHA+S1RYKEtvcmVhIFRyYWluIGVYcHJlc3MpXHViMjk0IEtPUkFJTFx1Yzc3NCBcdWM2YjRcdWM2MDFcdWQ1NThcdWIyOTQgXHViMzAwXHVkNTVjXHViYmZjXHVhZDZkIFx1YWNlMFx1YzE4ZFx1Y2NhMFx1YjNjNFx1Yzc3NFx1YmE3MCwgXHVjMTFjXHVjNmI4XHVhY2ZjIFx1YzhmY1x1YzY5NCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiBLVFgtXHVjMGIwXHVjYzljXHVjNzQwIFx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc1OCBcdWIzYzVcdWM3OTBcdWM4MDFcdWM3NzggXHVhZTMwXHVjMjIwXHViODVjIFx1YWMxY1x1YmMxY1x1YjQxYyBcdWM1ZjRcdWNjMjhcdWI4NWMgMzUwa21cL2hcdWFlNGNcdWM5YzAgXHVjMThkXHViM2M0XHViOTdjIFx1YjE5Mlx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM3YWMgXHVjMThkXHViM2M0XHViOTdjIFx1Y2Q1Y1x1YWNlMCA0MDBrbVwvaFx1YWU0Y1x1YzljMCBcdWM2MmNcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YzVmMFx1YWQ2YyBcdWFjMWNcdWJjMWNcdWM5MTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzU5MVx1Y2MyOFx1YjdjOVx1YzBhY1x1YzVjNVx1YzE4Y1x1YjI5NCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWNjMjhcdWI3YzlcdWFlMzBcdWM5YzBcdWI4NWMsIEtUWCBcdWM1ZjRcdWNjMjhcdWM3NTggXHVjNzg1XHVjZDljXHVhY2UwIFx1YWQwMFx1YjlhY1x1YzY0MCBcdWFjODBcdWMyMThcdWI5N2MgXHViMmY0XHViMmY5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWM1OTFcdWNjMjhcdWI3YzlcdWMwYWNcdWM1YzVcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjIFx1YzVmNFx1Y2MyOFx1YjI5NCBcdWM3OTBcdWM4MTUgXHVjODA0XHVjNWQwIFx1YWUzMFx1YzljMFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWJhNzAsIFx1YzU0NFx1Y2U2OFx1YzVkMCBcdWI1YTBcdWIwOThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVhZTMwXHVjOWMwXHVjNzU4IFx1YjNkOVx1Y2FiZFx1Yzc3NFx1YjA5OCBcdWMxMWNcdWNhYmRcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI0XHViYTcwLCBcdWIwOThcdWFjMDhcdWI1NGNcdWIzYzQgXHViM2Q5XHVjYWJkXHVjNzc0XHViMDk4IFx1YzExY1x1Y2FiZFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWNjMjhcdWI3YzlcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YWNmM1x1Yzc3NFx1YjA5OCBcdWIwOThcdWFjMDBcdWIyOTQgXHVhY2YzXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Y2Q5Y1x1YmMxY1x1YzJkY1x1YWMwNFx1YWNmYyBcdWIzYzRcdWNjMjlcdWMyZGNcdWFjMDRcdWIzYzQgXHViYWE4XHViNDUwIFx1YzgxNVx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSBcdWFjMDEgXHVjNWY0XHVjYzI4XHVhYzAwIFx1YWUzMFx1YzljMCBcdWIwYjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNCBcdWFkNmNcdWFjMDQgW3Q8c3ViPjE8XC9zdWI+LCB0PHN1Yj4yPFwvc3ViPl1cdWM2NDAsIFx1YjA5OFx1YWMwMFx1YWNlMCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHViYzI5XHVkNWE1IGQ8c3ViPjE8XC9zdWI+LCBkMlx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFstNkUsIDEzV11cdWIyOTQgXHVjMmRjXHVhYzA0IC02XHVjNWQwIFx1YjNkOVx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFlMzBcdWM5YzBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjI0XHVhY2UwLCBcdWMyZGNcdWFjMDQgMTNcdWM1ZDAgXHVjMTFjXHVjYWJkXHVjNzNjXHViODVjIFx1YWUzMFx1YzljMFx1Yjk3YyBcdWIwOThcdWFjMDBcdWIyOTQgXHVjNWY0XHVjYzI4XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YzJkY1x1YWMwNFx1YzVkMFx1YjI5NCBcdWFlMzBcdWM5YzAgXHViMGI0XHVjNzU4IFx1ZDNjOVx1ZDU4OSBcdWMxMjBcdWI4NWNcdWM1ZDBcdWMxMWMgXHViMzAwXHVhZTMwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWFlMzBcdWM5YzBcdWI5N2MgXHViNWEwXHViMDk4XHVhYzcwXHViMDk4IFx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NDAgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNWY0XHVjYzI4XHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWM1ZjRcdWNjMjhcdWM1ZDAgXHViYzI5XHVkNTc0XHViYzFiXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWNkOWNcdWJjMWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWMxMjBcdWI4NWNcdWFjMDAgXHVkNTYwXHViMmY5XHViNDFjXHViMmU0LiBcdWM1NDQgXHVhZGY4XHViOWJjIDFcdWM3NDAgXHVjNWY0XHVjYzI4Wy0yRSwyV11cdWFjMDAgXHVjNWY0XHVjYzI4IFstMVcsNFddXHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWI5YzlcdWQ2MDBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjliYyAyKGEpXHVjNjQwIDIoYilcdWIyOTQgXHViYWE4XHViNDUwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIDIoYilcdWIyOTQgXHVjMTIwXHViODVjXHViOTdjIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaHdhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk3cHg7IHdpZHRoOjI5MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgMS4gXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YzEyMFx1Yjg1YyBcdWQ1NjBcdWIyZjk8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2h3YTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI2cHg7IHdpZHRoOjYyNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgMi4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YzEyMFx1Yjg1YyBcdWQ1NjBcdWIyZjk8XC9wPlxyXG5cclxuPHA+S09SQUlMIFx1YzVmMFx1YWQ2Y1x1YzE4Y1x1YzdhNSBEci4gXHVjODhjXHViMjk0IFx1YWNlMFx1YzU5MVx1Y2MyOFx1YjdjOVx1YzBhY1x1YzVjNVx1YzE4Y1x1YzVkMFx1YzExYyBcdWJjZjRcdWFkMDBcdWQ1NThcdWIyOTQgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIyOThcdWI5YWNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBEci4gXHVjODhjXHViMjk0IFx1YzEyMFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhY2UwXHVjODE1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Y2MyOFx1YjdjOVx1Yzc0NCBcdWJjZjRcdWFkMDBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzc0IFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2Y2MgXHVjOWM4IFx1YWM4M1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWM2MDhcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YzEyMFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWJjZjRcdWFkMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWM4MTVcdWIzYzRcdWI4NWMgXHViOWU0XHVjNmIwIFx1YWUzOFx1YjJlNC4gRHIuIFx1Yzg4Y1x1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWY0XHVjYzI4XHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWM1ZjRcdWNjMjhcdWM1ZDAgXHViOWM5XHVkNzg4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM4MTVcdWMyZGNcdWM1ZDAgXHVjZDljXHViYzFjXHVkNTU4XHVhY2UwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzEyMFx1Yjg1Y1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIERyLiBcdWM4OGNcdWI5N2MgXHViM2M0XHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHQ8c3ViPjE8XC9zdWI+ZDxzdWI+MTxcL3N1Yj50PHN1Yj4yPFwvc3ViPmQ8c3ViPjI8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gdDxzdWI+MTxcL3N1Yj5cdWFjZmMgdDxzdWI+MjxcL3N1Yj5cdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwJm5ic3A7LTEsMDAwLDAwMCAmbGU7IHQ8c3ViPjE8XC9zdWI+ICZsdDsgMCAmbHQ7IHQ8c3ViPjI8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLCBkPHN1Yj4xPFwvc3ViPixkPHN1Yj4yPFwvc3ViPiAmaXNpbjsge0UsIFd9IFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMTIwXHViODVjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLVFggVHJhaW4gRGVwb3QiLCJkZXNjcmlwdGlvbiI6IjxwPktUWCAoS29yZWEgVHJhaW4gZVhwcmVzcyksIEtvcmVhJnJzcXVvO3MgaGlnaC1zcGVlZCByYWlsIHN5c3RlbSBvcGVyYXRlZCBieSBLT1JBSUwsIGNvbm5lY3RzIHRoZSBjYXBpdGFsIFNlb3VsIHRvIHNldmVyYWwgbWFqb3IgY2l0aWVzIG9mIHRoZSBLb3JlYW4gUGVuaW5zdWxhLiBLT1JBSUwmcnNxdW87cyBtb3N0IHJlY2VudCB0cmFpbiBzZXRzIEtUWC1JSSwgd2hpY2ggd2VyZSBkZXZlbG9wZWQgaW4gS29yZWEsIGNhbiB0cmF2ZWwgYXQgb3ZlciAzNTAga21cL2guIFRoZSBuZXh0LWdlbmVyYXRpb24gdGVzdCB0cmFpbiBpcyBjdXJyZW50bHkgYmVpbmcgZGV2ZWxvcGVkLCBhbmQgdGhlIHRyYWluIGlzIHBsYW5uZWQgdG8gYmUgYWJsZSB0byB0cmF2ZWwgYXQgb3ZlciA0MDAga21cL2ggYnkgMjAxMi4gS1RYIEdveWFuZyBUcmFpbiBEZXBvdCwgd2hpY2ggaXMgbG9jYXRlZCBiZWhpbmQgSGFlbmdzaW4gU3RhdGlvbiwgaXMgb25lIG9mIHRoZSBiaWdnZXN0IHRyYWluIGRlcG90cyBpbiBLb3JlYS4gVGhlIHRyYWluIGRlcG90IGNvbnNpc3RzIG9mIGEgc2V0IG9mIHBhcmFsbGVsIHRyYWNrcyBmb3Igc3RvcmluZyBLVFggdHJhaW5zIGFuZCBmYWNpbGl0aWVzIGZvciBjYXJyeWluZyBvdXQgcmVwYWlyIGpvYnMuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkFsbCB0cmFpbnMgd2hvc2UgaG9tZSBpcyBLVFggR295YW5nIFRyYWluIERlcG90IGVudGVyIHRoZSBkZXBvdCB1bnRpbCB0aGUgbWlkZGxlIG9mIHRoZSBuaWdodCBhbmQgbGVhdmUgaXQgaW4gdGhlIG1vcm5pbmcuIEVhY2ggdHJhaW4gbWlnaHQgZW50ZXIgdGhlIGRlcG90IGVpdGhlciBmcm9tIHRoZSBlYXN0ZXJuIHNpZGUgb3IgZnJvbSB0aGUgd2VzdGVybiBzaWRlIGFuZCBtaWdodCBsZWF2ZSB0aGUgZGVwb3QgdG8gdGhlIGVhc3Rlcm4gc2lkZSBvciB0byB0aGUgd2VzdGVybiBzaWRlLiBUaGUgZGlyZWN0aW9uIGZyb20gd2hpY2ggaXQgZW50ZXJzIG9yIHRvIHdoaWNoIGl0IGxlYXZlcyB0aGUgZGVwb3QsIGhvd2V2ZXIsIGlzIGZpeGVkLiBBbHNvIHRoZSBhcnJpdmFsIGFuZCBkZXBhcnR1cmUgdGltZXMgYXJlIGZpeGVkLiBIZW5jZSwgdGhlIHRyYWluIGlzIGxhYmVsZWQgd2l0aCB0aGUgdGltZSBpbnRlcnZhbCBbdDxzdWI+MTxcL3N1Yj4sdDxzdWI+MjxcL3N1Yj5dIGluIHdoaWNoIGl0IHN0YXlzIGluIHRoZSBkZXBvdCBhbmQgYW4gYXJyaXZhbCBhbmQgZGVwYXJ0dXJlIGRpcmVjdGlvbiBkPHN1Yj4xPFwvc3ViPiBhbmQgZDxzdWI+MjxcL3N1Yj4sIHJlc3BlY3RpdmVseS4gRm9yIGV4YW1wbGUsIGEgdHJhaW4gbGFiZWxlZCBbLTZFLDEzV10gaXMgYSB0cmFpbiB0aGF0IGVudGVycyB0aGUgZGVwb3QgYXQgdGltZSAtNiBmcm9tIHRoZSBlYXN0ZXJuIHNpZGUgYW5kIGxlYXZlcyB0aGUgZGVwb3QgYXQgdGltZSAxMyB0byB0aGUgd2VzdGVybiBzaWRlLiBJbiB0aGUgbWVhbndoaWxlLCBpdCBzdG9wcyBvbiBvbmUgb2Ygc2V2ZXJhbCBwYXJhbGxlbCB0cmFja3MgaW4gdGhlIGRlcG90LiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gdHJhaW5zIGFycml2ZSBmcm9tIHRoZSBzYW1lIGRpcmVjdGlvbiBhdCB0aGUgc2FtZSB0aW1lIG9yIGRlcGFydCB0byB0aGUgc2FtZSBkaXJlY3Rpb24gYXQgdGhlIHNhbWUgdGltZS4gVGhlcmUgbWlnaHQgYmUgc2V2ZXJhbCB0cmFpbnMgd2FpdGluZyBhdCB0aGUgc2FtZSB0cmFjay4gRWFjaCB0cmFpbiBpcyBhc3NpZ25lZCB0byBhIHRyYWNrIHN1Y2ggdGhhdCBpdCBjYW4gbGVhdmUgdGhlIGRlcG90IG9uIHRpbWUgd2l0aG91dCBiZWluZyBibG9ja2VkIGJ5IG90aGVyIHRyYWlucy4gVGhhdCBpcywgdGhlIGFzc2lnbm1lbnQgb2YgRmlndXJlIDEgaXMgbm90IGZlYXNpYmxlLCBzaW5jZSB0cmFpbiBbLTJFLDJXXSB3b3VsZCBiZSBibG9ja2VkIGJ5IHRyYWluIFstMVcsNFddLiBUaGUgYXNzaWdubWVudHMgaW4gRmlndXJlcyAyKGEpIGFuZCAyKGIpIGFyZSBib3RoIGZlYXNpYmxlLiBIb3dldmVyLCBhbiBpbnRlcmVzdGluZyBhc3NpZ25tZW50IGlzIHRoZSBvbmUgaW4gRmlndXJlIDIoYiksIHdoaWNoIHVzZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRyYWNrcy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaHdhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk3cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDoyOTBweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gQW4gaW5mZWFzaWJsZSB0cmFjayBhc3NpZ25tZW50Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2h3YTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI2cHg7IG9wYWNpdHk6MC45OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NjI0cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIDIuIEZlYXNpYmxlIHRyYWNrIGFzc2lnbm1lbnRzJm5ic3A7PFwvcD5cclxuXHJcbjxwPkl0IGlzIHBsYW5uZWQgdG8gaW5jcmVhc2UgdGhlIG51bWJlciBvZiBLVFggdHJhaW5zIHdob3NlIGhvbWUgaXMgS1RYIEdveWFuZyBUcmFpbiBEZXBvdC4gRHIuIENod2EsIHdobyBpcyB0aGUgUHJlc2lkZW50IG9mIEtPUkFJTCBSZXNlYXJjaCBJbnN0aXR1dGUsIGZvcmVzZWVzIHRoYXQgaXQgbWlnaHQgY2F1c2UgYSBkaWZmaWN1bHR5IGluIHN0b3JpbmcgdHJhaW5zIGluIHRoZSBkZXBvdCBkdWUgdG8gdGhlIGxpbWl0IG9uIHRoZSBudW1iZXIgb2YgdHJhY2tzLiBUaGUgbGVuZ3RoIG9mIGEgdHJhY2sgd2lsbCBiZSBubyBwcm9ibGVtIHNpbmNlIGVhY2ggdHJhY2sgaXMgbG9uZyBlbm91Z2ggdG8gc3RvcmUgZXZlbiBhbGwgdGhlIHRyYWlucy4gRHIuIENod2EgaXMgZWFnZXIgdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0cmFja3MgdG8gc3RvcmUgYWxsIHRoZSB0cmFpbnMgc3VjaCB0aGF0IGVhY2ggdHJhaW4gY2FuIGxlYXZlIHRoZSBkZXBvdCBvbiB0aW1lIHdpdGhvdXQgYmVpbmcgYmxvY2tlZCBieSBvdGhlciB0cmFpbnMuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbiBoZWxwIGhpbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGV4dCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBhbiBpbnRlZ2VyIG4gd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIHRyYWlucywgd2hlcmUgMSAmbGU7IG4gJmxlOyAxMCwwMDAuIEluIHRoZSBmb2xsb3dpbmcgbiBsaW5lcywgZWFjaCBsaW5lIGNvbnRhaW5zIGEgdHJhaW4gbGFiZWwgdDxzdWI+MTxcL3N1Yj5kPHN1Yj4xPFwvc3ViPnQ8c3ViPjI8XC9zdWI+ZDxzdWI+MjxcL3N1Yj4sIHdoaWNoIHJlcHJlc2VudHMgYSB0cmFpbiB0aGF0IGVudGVycyB0aGUgZGVwb3QgYXQgdGltZSB0PHN1Yj4xPFwvc3ViPiBmcm9tIHRoZSBkaXJlY3Rpb24gZDxzdWI+MTxcL3N1Yj4gYW5kIGxlYXZlcyB0aGUgZGVwb3QgYXQgdGltZSB0PHN1Yj4yPFwvc3ViPiB0byB0aGUgZGlyZWN0aW9uIGQ8c3ViPjI8XC9zdWI+LCB3aGVyZSB0PHN1Yj4xPFwvc3ViPiBhbmQgdDxzdWI+MjxcL3N1Yj4gYXJlIGludGVnZXJzIHN1Y2ggdGhhdCAtMSwwMDAsMDAwICZsZTsgdDxzdWI+MTxcL3N1Yj4gJmx0OyAwICZsdDsgdDxzdWI+MjxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAgYW5kIGQ8c3ViPjE8XC9zdWI+LGQ8c3ViPjI8XC9zdWI+ICZpc2luOyB7RSxXfS4gRXZlcnkgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgbm8gd2hpdGVzcGFjZXMgZXhjZXB0IHRoZSBuZXdsaW5lIGNoYXJhY3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZSB0aGF0IGNvbnRhaW5zIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0cmFja3MgdGhhdCBEci4gQ2h3YSBpcyBlYWdlciB0byBrbm93LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2010 J번