시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB41817311841.549%

문제

국방 과학 연구소 (Korea Defense and Science Institute, KDSI) 에서는 최근 몇 년간 군인 개인이 착용할 새로운 장비를 꾸준히 개발하고 있고, 얼마 전에 N 종류의 장비를 출시했다.

KDSI는 새로 만든 모든 장비의 성능을 평가했고, 5가지 범주로 나눠서 평가를 해 점수로 나타냈다. 다섯 가지 범주는 공격 향상, 방어 향상, 시력 향상, 휴대성, 사용 편이성이다. 모든 점수는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다. 따라서, 모든 장비는 정수 다섯개로 나타낼 수 있다.

KDSI에서는 군인들의 능력의 평균과 비용 문제 때문에, 군인 한 명이 착용할 수 있는 장비의 개수를 K개로 제한했다. 만약, 한 군인이 장비를 하나만 착용한 경우에, 그 장비의 점수만큼 능력이 향상된다. 두 개 이상 착용한 경우에는 각 범주마다 독립적으로 능력이 향상되며, 착용한 장치의 점수의 최댓값만큼 능력이 향상된다. 예를 들어, 장비 a와 b의 시력 향상 점수가 10과 15일때, 두 장비를 착용하면 최댓값인 15만큼 시력이 향상된다. 이때, 최대 점수 15를 범주의 확장 점수라고 한다. 따라서, 이 예에서 {a, b}의 시력 향상 확장 점수는 15가 된다.

KDSI는 군인 한 명이 장비를 K개 착용했을 때, 가장 능력 향상이 많이 되는 조합을 찾으려고 한다. 특수 목적 군인의 경우에는 특정 범주의 점수가 훨씬 더 중요하다. 하지만, 범용성을 위해 각 범주의 확장 점수의 합이 최대가되는 조합을 찾으려고 한다. N개의 장비 중에서 확장 점수의 합이 최대가 되는 장비 K개 조합을 찾는 프로그램을 작성하시오.

장비가 N개를 {1, ..., N}로, 각 장비의 점수 Ri를 다섯 정수 Ri = (ri,1, ri,2, ri,3, ri,4, ri,5) (모든 i=1,...,N과 j=1,...,5에 대해서 0 ≤ ri,j ≤ 10,000)로 나타낼 수 있다. 이때, K (1 ≤ K ≤ N)가 주어졌을 때, 확장 점수의 합이 가장 큰 장비 K개를 찾아야 한다.

예를 들어, N=4, K=2이고, Ri가 다음과 같은 경우가 있다.

  • R1 = (30, 30, 30, 30, 0)
  • R2 = (50, 0, 0, 0, 0)
  • R3 = (0, 50, 0, 50, 10)
  • R4 = (0, 0, 50, 0, 20)

R1과 R3을 착용하면 향상 점수는 30+50+30+50+10 = 170이 되고, 이 점수가 가능한 값 중 가장 큰 값이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다섯개가 주어지며, 이 정수는 각 장비의 점수 ri,1, ri,2, ri,3, ri,4, ri,5를 나타낸다. 인접한 두 정수 사이에는 빈 칸이 하나 있다.

출력

각 테스트 케이스 마다, 장비 N개중 K개를 착용했을 때, 가장 큰 향상 점수의 합을 출력한다.

예제 입력 1

2
4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20
5 1
10 20 60 0 0
0 0 20 50 30
30 50 20 20 0
10 10 10 20 30
30 0 20 10 20

예제 출력 1

170
120
W3sicHJvYmxlbV9pZCI6Ijg5MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWJlNDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWQ2ZFx1YmMyOSBcdWFjZmNcdWQ1NTkgXHVjNWYwXHVhZDZjXHVjMThjIChLb3JlYSBEZWZlbnNlIGFuZCBTY2llbmNlIEluc3RpdHV0ZSwgS0RTSSkgXHVjNWQwXHVjMTFjXHViMjk0IFx1Y2Q1Y1x1YWRmYyBcdWJhODcgXHViMTQ0XHVhYzA0IFx1YWQ3MFx1Yzc3OCBcdWFjMWNcdWM3NzhcdWM3NzQgXHVjYzI5XHVjNmE5XHVkNTYwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM3YTVcdWJlNDRcdWI5N2MgXHVhZmI4XHVjOTAwXHVkNzg4IFx1YWMxY1x1YmMxY1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzViY1x1YjljOCBcdWM4MDRcdWM1ZDAgTiBcdWM4ODVcdWI5NThcdWM3NTggXHVjN2E1XHViZTQ0XHViOTdjIFx1Y2Q5Y1x1YzJkY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+S0RTSVx1YjI5NCBcdWMwYzhcdWI4NWMgXHViOWNjXHViNGUwIFx1YmFhOFx1YjRlMCBcdWM3YTVcdWJlNDRcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQ0IFx1ZDNjOVx1YWMwMFx1ZDU4OFx1YWNlMCwgNVx1YWMwMFx1YzljMCBcdWJjOTRcdWM4ZmNcdWI4NWMgXHViMDk4XHViMjIwXHVjMTFjIFx1ZDNjOVx1YWMwMFx1Yjk3YyBcdWQ1NzQgXHVjODEwXHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1YjJlNC4gXHViMmU0XHVjMTJmIFx1YWMwMFx1YzljMCBcdWJjOTRcdWM4ZmNcdWIyOTQgXHVhY2Y1XHVhY2E5IFx1ZDVhNVx1YzBjMSwgXHViYzI5XHVjNWI0IFx1ZDVhNVx1YzBjMSwgXHVjMmRjXHViODI1IFx1ZDVhNVx1YzBjMSwgXHVkNzM0XHViMzAwXHVjMTMxLCBcdWMwYWNcdWM2YTkgXHVkM2I4XHVjNzc0XHVjMTMxXHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODEwXHVjMjE4XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmFhOFx1YjRlMCBcdWM3YTVcdWJlNDRcdWIyOTQgXHVjODE1XHVjMjE4IFx1YjJlNFx1YzEyZlx1YWMxY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+S0RTSVx1YzVkMFx1YzExY1x1YjI5NCBcdWFkNzBcdWM3NzhcdWI0ZTRcdWM3NTggXHViMmE1XHViODI1XHVjNzU4IFx1ZDNjOVx1YWRlMFx1YWNmYyBcdWJlNDRcdWM2YTkgXHViYjM4XHVjODFjIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhZDcwXHVjNzc4IFx1ZDU1YyBcdWJhODVcdWM3NzQgXHVjYzI5XHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjN2E1XHViZTQ0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBLXHVhYzFjXHViODVjIFx1YzgxY1x1ZDU1Y1x1ZDU4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWQ1NWMgXHVhZDcwXHVjNzc4XHVjNzc0IFx1YzdhNVx1YmU0NFx1Yjk3YyBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjYzI5XHVjNmE5XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMCwgXHVhZGY4IFx1YzdhNVx1YmU0NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5Y2NcdWQwN2MgXHViMmE1XHViODI1XHVjNzc0IFx1ZDVhNVx1YzBjMVx1YjQxY1x1YjJlNC4gXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjYzI5XHVjNmE5XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYzk0XHVjOGZjXHViOWM4XHViMmU0IFx1YjNjNVx1YjliZFx1YzgwMVx1YzczY1x1Yjg1YyBcdWIyYTVcdWI4MjVcdWM3NzQgXHVkNWE1XHVjMGMxXHViNDE4XHViYTcwLCBcdWNjMjlcdWM2YTlcdWQ1NWMgXHVjN2E1XHVjZTU4XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWI5Y2NcdWQwN2MgXHViMmE1XHViODI1XHVjNzc0IFx1ZDVhNVx1YzBjMVx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjN2E1XHViZTQ0IGFcdWM2NDAgYlx1Yzc1OCBcdWMyZGNcdWI4MjUgXHVkNWE1XHVjMGMxIFx1YzgxMFx1YzIxOFx1YWMwMCAxMFx1YWNmYyAxNVx1Yzc3Y1x1YjU0YywgXHViNDUwIFx1YzdhNVx1YmU0NFx1Yjk3YyBcdWNjMjlcdWM2YTlcdWQ1NThcdWJhNzQgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzc4IDE1XHViOWNjXHVkMDdjIFx1YzJkY1x1YjgyNVx1Yzc3NCBcdWQ1YTVcdWMwYzFcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOCAxNVx1Yjk3YyBcdWJjOTRcdWM4ZmNcdWM3NTggXHVkNjU1XHVjN2E1IFx1YzgxMFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNzc0IFx1YzYwOFx1YzVkMFx1YzExYyB7YSwgYn1cdWM3NTggXHVjMmRjXHViODI1IFx1ZDVhNVx1YzBjMSBcdWQ2NTVcdWM3YTUgXHVjODEwXHVjMjE4XHViMjk0IDE1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+S0RTSVx1YjI5NCBcdWFkNzBcdWM3NzggXHVkNTVjIFx1YmE4NVx1Yzc3NCBcdWM3YTVcdWJlNDRcdWI5N2MgS1x1YWMxYyBcdWNjMjlcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViMmE1XHViODI1IFx1ZDVhNVx1YzBjMVx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHViNDE4XHViMjk0IFx1Yzg3MFx1ZDU2OVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQyYjlcdWMyMTggXHViYWE5XHVjODAxIFx1YWQ3MFx1Yzc3OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkMmI5XHVjODE1IFx1YmM5NFx1YzhmY1x1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgXHVkNmU4XHVjNTJjIFx1YjM1NCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYzk0XHVjNmE5XHVjMTMxXHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHViYzk0XHVjOGZjXHVjNzU4IFx1ZDY1NVx1YzdhNSBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMFx1YjQxOFx1YjI5NCBcdWM4NzBcdWQ1NjlcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gTlx1YWMxY1x1Yzc1OCBcdWM3YTVcdWJlNDQgXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDY1NVx1YzdhNSBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVjN2E1XHViZTQ0IEtcdWFjMWMgXHVjODcwXHVkNTY5XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM3YTVcdWJlNDRcdWFjMDAgTlx1YWMxY1x1Yjk3YyB7MSwgLi4uLCBOfVx1Yjg1YywgXHVhYzAxIFx1YzdhNVx1YmU0NFx1Yzc1OCBcdWM4MTBcdWMyMTggUjxzdWI+aTxcL3N1Yj5cdWI5N2MgXHViMmU0XHVjMTJmIFx1YzgxNVx1YzIxOCBSPHN1Yj5pPFwvc3ViPiA9IChyPHN1Yj5pLDE8XC9zdWI+LCByPHN1Yj5pLDI8XC9zdWI+LCByPHN1Yj5pLDM8XC9zdWI+LCByPHN1Yj5pLDQ8XC9zdWI+LCByPHN1Yj5pLDU8XC9zdWI+KSAoXHViYWE4XHViNGUwIGk9MSwuLi4sTlx1YWNmYyBqPTEsLi4uLDVcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDAgJmxlOyByPHN1Yj5pLGo8XC9zdWI+ICZsZTsgMTAsMDAwKVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBLICgxICZsZTsgSyAmbGU7IE4pXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDY1NVx1YzdhNSBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjN2E1XHViZTQ0IEtcdWFjMWNcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTj00LCBLPTJcdWM3NzRcdWFjZTAsIFJpXHVhYzAwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5SPHN1Yj4xPFwvc3ViPiA9ICgzMCwgMzAsIDMwLCAzMCwgMCk8XC9saT5cclxuXHQ8bGk+UjxzdWI+MjxcL3N1Yj4gPSAoNTAsIDAsIDAsIDAsIDApPFwvbGk+XHJcblx0PGxpPlI8c3ViPjM8XC9zdWI+ID0gKDAsIDUwLCAwLCA1MCwgMTApPFwvbGk+XHJcblx0PGxpPlI8c3ViPjQ8XC9zdWI+ID0gKDAsIDAsIDUwLCAwLCAyMCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5SPHN1Yj4xPFwvc3ViPlx1YWNmYyBSPHN1Yj4zPFwvc3ViPlx1Yzc0NCBcdWNjMjlcdWM2YTlcdWQ1NThcdWJhNzQgXHVkNWE1XHVjMGMxIFx1YzgxMFx1YzIxOFx1YjI5NCAzMCs1MCszMCs1MCsxMCA9IDE3MFx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWMxMiBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLDAwMCwgMSAmbGU7IEsgJmxlOyBOKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMTggXHViMmU0XHVjMTJmXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFjMDEgXHVjN2E1XHViZTQ0XHVjNzU4IFx1YzgxMFx1YzIxOCByPHN1Yj5pLDE8XC9zdWI+LCByPHN1Yj5pLDI8XC9zdWI+LCByPHN1Yj5pLDM8XC9zdWI+LCByPHN1Yj5pLDQ8XC9zdWI+LCByPHN1Yj5pLDU8XC9zdWI+XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWM4MTVcdWMyMTggXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1YzdhNVx1YmU0NCBOXHVhYzFjXHVjOTExIEtcdWFjMWNcdWI5N2MgXHVjYzI5XHVjNmE5XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1YTVcdWMwYzEgXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiODkwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVxdWlwbWVudCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEtvcmVhIERlZmVuc2UgYW5kIFNjaWVuY2UgSW5zdGl0dXRlLCBzaG9ydGx5IEtEU0ksIGhhcyBiZWVuIHB1dHRpbmcgY29uc3RhbnQgZWZmb3J0IGludG8gbmV3IGVxdWlwbWVudCBmb3IgaW5kaXZpZHVhbCBzb2xkaWVycyBmb3IgcmVjZW50IHllYXJzLCBhbmQgYXQgbGFzdCByZWxlYXNlZCBOIG5ldyB0eXBlcyBvZiBlcXVpcG1lbnQuIEtEU0kgaGFzIGFscmVhZHkgZG9uZSBldmFsdWF0aW9uIG9mIGVhY2ggb2YgdGhlIE4gdHlwZXMgb2YgZXF1aXBtZW50LCBmaW5hbGx5IHJlc3VsdGluZyBpbiBzY29yZXMgaW4gZml2ZSBjYXRlZ29yaWVzOiBhdHRhY2sgaW1wcm92ZW1lbnQsIGRlZmVuc2UgaW1wcm92ZW1lbnQsIHZpc2lvbiBpbXByb3ZlbWVudCwgcG9ydGFiaWxpdHksIGFuZCBlYXNpbmVzcyBvZiB1c2FnZS4gVGhlIHNjb3JlIGluIGVhY2ggY2F0ZWdvcnkgaXMgcXVhbnRpZmllZCBhcyBhbiBpbnRlZ2VyIGluIHRoZSByYW5nZSAwIHRvIDEwLDAwMCwgYW5kIHRoZSByYXRpbmcgb2YgZWFjaCB0eXBlIG9mIGVxdWlwbWVudCBpcyB0aHVzIHJlcHJlc2VudGVkIGFzIGEgc2VxdWVuY2Ugb2YgZml2ZSBpbnRlZ2Vycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gY29uc2lkZXJhdGlvbiBvZiBjb3N0cyBhbmQgY2FwYWJpbGl0eSBvZiBhdmVyYWdlIGluZGl2aWR1YWwgc29sZGllcnMsIEtEU0kgYWxzbyByZXBvcnRlZCB0aGF0IGVhY2ggc29sZGllciB3aWxsIGJlIGFibGUgdG8gaW5zdGFsbCBhdCBtb3N0IEsgdHlwZXMgb2YgZXF1aXBtZW50IG9uIGhpcyBib2R5IHRvIGV4dGVuZCBoaXMgYWJpbGl0eS4gSWYgYSBzaW5nbGUgdHlwZSBpcyBpbnN0YWxsZWQgb24gYSBzb2xkaWVyLCB0aGVuIGhpcyBhYmlsaXR5IGluIGVhY2ggY2F0ZWdvcnkgaXMgZXh0ZW5kZWQgYnkgdGhlIHNwZWNpZmllZCBzY29yZSBvZiB0aGF0IHR5cGUuIE1vcmVvdmVyLCBpZiBhIHNvbGRpZXIgaW5zdGFsbHMgbW9yZSB0aGFuIG9uZSB0eXBlIG9mIGVxdWlwbWVudCwgdGhlbiBoaXMgYWJpbGl0eSBpbiBlYWNoIGNhdGVnb3J5IGlzIGV4dGVuZGVkIGJ5IHRoZSBtYXhpbXVtIHNjb3JlIG9mIHRoZSBjaG9zZW4gdHlwZXMgaW4gdGhhdCBjYXRlZ29yeS4gRm9yIGV4YW1wbGUsIGlmIHRoZSB2aXNpb24gaW1wcm92ZW1lbnQgc2NvcmVzIG9mIHR5cGUgYSBhbmQgdHlwZSBiIGFyZSAxMCBhbmQgMTUsIHJlc3BlY3RpdmVseSwgdGhlbiBpbnN0YWxsaW5nIGEgY29tYmluYXRpb24gb2YgdHdvIHR5cGVzIGEgYW5kIGIgd2lsbCByZXN1bHQgaW4gYSB2aXNpb24gaW1wcm92ZW1lbnQgYnkgdGhlaXIgbWF4aW11bSBzY29yZSAxNS4gV2UgY2FsbCB0aGUgbWF4aW11bSBzY29yZSAxNSB0aGUgZXh0ZW5zaW9uIHNjb3JlIG9mIGEgY2F0ZWdvcnk7IHNvLCB0aGUgZXh0ZW5zaW9uIHNjb3JlIG9mIHZpc2lvbiBpbXByb3ZlbWVudCBmb3IgY29tYmluYXRpb24ge2EsIGJ9IGlzIDE1IGluIHRoaXMgZXhhbXBsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+S0RTSSBub3cgc3RhcnRlZCBkZXZpc2luZyBhIHdheSBvZiBmaW5kaW5nIGFuIG9wdGltYWwgY29tYmluYXRpb24gb2YgSyB0eXBlcyBvZiBlcXVpcG1lbnQgZm9yIGJlc3QgcGVyZm9ybWFuY2Ugb2YgaW5kaXZpZHVhbCBzb2xkaWVycy4gV2hpbGUgYSBmb3JjZSBjYW4gc29tZXRpbWVzIGJlIG9mIGEgc3BlY2lhbCBwdXJwb3NlIHNvIHRoYXQgYSBjZXJ0YWluIGNhdGVnb3J5IHdvdWxkIGJlIG1vcmUgaW1wb3J0YW50IHRoYW4gdGhlIG90aGVycywgZXZlcnkgc2luZ2xlIGNhdGVnb3J5IGlzLCBob3dldmVyLCByZWdhcmRlZCBlcXVhbGx5IGltcG9ydGFudCBpbiBnZW5lcmFsLiBGb3IgdGhpcyBnZW5lcmFsIHB1cnBvc2UsIEtEU0kgZGVmaW5lZCB0aGUgb2JqZWN0aXZlIHNjb3JlIG9mIGEgY29tYmluYXRpb24gb2YgZXF1aXBtZW50IHRvIGJlIHRoZSBzdW0gb2YgdGhlIGV4dGVuc2lvbiBzY29yZXMgb2YgdGhlIGZpdmUgY2F0ZWdvcmllcyBmb3IgdGhlIGNvbWJpbmF0aW9uLiBLRFNJIHRodXMgd2FudHMgdG8gZmluZCBhIGJlc3QgY29tYmluYXRpb24gb2YgSyB0eXBlcyBvZiBlcXVpcG1lbnQgc3VjaCB0aGF0IGl0cyBvYmplY3RpdmUgc2NvcmUgaXMgbWF4aW1pemVkIGFtb25nIGFsbCBwb3NzaWJsZSBjb21iaW5hdGlvbnMgb2YgSyB0eXBlcy4gWW91IGFyZSBhc2tlZCBieSBLRFNJIHRvIGRldmlzZSBhbmQgd3JpdGUgYSBjb21wdXRlciBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG9iamVjdGl2ZSBzY29yZSBvZiBhIGJlc3QgY29tYmluYXRpb24gb2YgSyB0eXBlcyBvZiBlcXVpcG1lbnQsIHRoYXQgaXMsIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG9iamVjdGl2ZSBzY29yZSBmb3IgYWxsIHBvc3NpYmxlIGNvbWJpbmF0aW9ucyBvZiBLIHR5cGVzIGFtb25nIHRoZSBnaXZlbiBOIHR5cGVzIG9mIGVxdWlwbWVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UHV0IGRpZmZlcmVudGx5LCB5b3UgYXJlIGdpdmVuIE4gdHlwZXMgb2YgZXF1aXBtZW50IHsxLCAuLi4sIE59IGFuZCB0aGVpciByYXRpbmdzIFI8c3ViPmk8XC9zdWI+IHJlcHJlc2VudGVkIGJ5IGZpdmUgaW50ZWdlcnMgUjxzdWI+aTxcL3N1Yj4gPSAocjxzdWI+aSwxPFwvc3ViPiwgcjxzdWI+aSwyPFwvc3ViPiwgcjxzdWI+aSwzPFwvc3ViPiwgcjxzdWI+aSw0PFwvc3ViPiwgcjxzdWI+aSw1PFwvc3ViPikgd2l0aCAwICZsZTsgcjxzdWI+aSxqPFwvc3ViPiAmbGU7IDEwLDAwMCBmb3IgZWFjaCBpLCAuLi4sIE4gYW5kIGogPSAxLCAuLi4sIDUuIEdpdmVuIGFub3RoZXIgbmF0dXJhbCBudW1iZXIgSyAoMSAmbGU7IEsgJmxlOyBOKSwgeW91ciBwcm9ncmFtIGhhcyB0byBjb21wdXRlIHRoZSBvYmplY3RpdmUgc2NvcmUgb2YgYSBiZXN0IGNvbWJpbmF0aW9uIG9mIEsgdHlwZXMgb2YgZXF1aXBtZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgYW4gaW5wdXQgaW5zdGFuY2UgaW4gd2hpY2ggTiA9IDQsIEsgPSAyLCBhbmQgZWFjaCBSPHN1Yj5pPFwvc3ViPiBpcyBnaXZlbiBhcyBiZWxvdzombmJzcDs8XC9wPlxyXG5cclxuPHA+UjxzdWI+MTxcL3N1Yj4gPSAoMzAsIDMwLCAzMCwgMzAsIDApJm5ic3A7PGJyIFwvPlxyXG5SPHN1Yj4yPFwvc3ViPiA9ICg1MCwgMCwgMCwgMCwgMCkmbmJzcDs8YnIgXC8+XHJcblI8c3ViPjM8XC9zdWI+ID0gKDAsIDUwLCAwLCA1MCwgMTApJm5ic3A7PGJyIFwvPlxyXG5SPHN1Yj40PFwvc3ViPiA9ICgwLCAwLCA1MCwgMCwgMjApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVuLCBjaG9vc2luZyBSPHN1Yj4xPFwvc3ViPiBhbmQgUjxzdWI+MzxcL3N1Yj4gZm9ybXMgYSBiZXN0IGNvbWJpbmF0aW9uIG9mIHR3byB0eXBlcyB7MSwgM30gYW5kIHlpZWxkcyB0aGUgb2JqZWN0aXZlIHNjb3JlIDMwKzUwKzMwKzUwKzEwID0gMTcwLCB3aGljaCB3aWxsIGJlIHRoZSBhbnN3ZXIgb2YgYSBjb3JyZWN0IHByb2dyYW0uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIFQgb2YgdGVzdCBjYXNlcyBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEZyb20gdGhlIHNlY29uZCBsaW5lLCBlYWNoIHRlc3QgY2FzZSBpcyBnaXZlbiBpbiBvcmRlciwgY29uc2lzdGluZyBvZiB0aGUgZm9sbG93aW5nOiBhIHRlc3QgY2FzZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyAxMCwwMDApIGFuZCBLICgxICZsZTsgSyAmbGU7IE4pIGluIGl0cyBmaXJzdCBsaW5lLCBhbmQgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcyBlYWNoIG9mIHdoaWNoIGNvbnNpc3RzIG9mIGZpdmUgaW50ZWdlcnMgaW5jbHVzaXZlbHkgYmV0d2VlbiAwIGFuZCAxMCwwMDAsIHJlcHJlc2VudGluZyB0aGUgZml2ZSBzY29yZXMgcjxzdWI+aSwxPFwvc3ViPiwgcjxzdWI+aSwyPFwvc3ViPiwgcjxzdWI+aSwzPFwvc3ViPiwgcjxzdWI+aSw0PFwvc3ViPiwgYW5kIHI8c3ViPmksNTxcL3N1Yj4gb2YgZWFjaCB0eXBlIGkgb2YgZXF1aXBtZW50IGZvciBpID0gMSwgLi4uLCBOIGluIG9yZGVyLiBUd28gY29uc2VjdXRpdmUgaW50ZWdlcnMgaW4gb25lIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSBhbmQgdGhlcmUgaXMgbm8gZW1wdHkgbGluZSBiZXR3ZWVuIHR3byBjb25zZWN1dGl2ZSB0ZXN0IGNhc2VzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG9iamVjdGl2ZSBzY29yZSBvZiBhIGJlc3QgY29tYmluYXRpb24gb2YgSyB0eXBlcyBvZiBlcXVpcG1lbnQ7IHRoZSBtYXhpbXVtIHBvc3NpYmxlIG9iamVjdGl2ZSBzY29yZSBmb3IgYWxsIHBvc3NpYmxlIGNvbWJpbmF0aW9ucyBvZiBLIHR5cGVzIGFtb25nIHRoZSBnaXZlbiBOIHR5cGVzIG9mIGVxdWlwbWVudCBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgdGVzdCBjYXNlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2011 D번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: cheetose