시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 257 86 60 34.682%

문제

국방 과학 연구소 (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+S0RTSVx1YzVkMFx1YzExY1x1YjI5NCBcdWFkNzBcdWM3NzhcdWI0ZTRcdWM3NTggXHViMmE1XHViODI1XHVjNzU4IFx1ZDNjOVx1YWRlMFx1YWNmYyBcdWJlNDRcdWM2YTkgXHViYjM4XHVjODFjIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhZDcwXHVjNzc4IFx1ZDU1YyBcdWJhODVcdWM3NzQgXHVjYzI5XHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjN2E1XHViZTQ0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBLXHVhYzFjXHViODVjIFx1YzgxY1x1ZDU1Y1x1ZDU4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWQ1NWMgXHVhZDcwXHVjNzc4XHVjNzc0IFx1YzdhNVx1YmU0NFx1Yjk3YyBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjYzI5XHVjNmE5XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMCwgXHVhZGY4IFx1YzdhNVx1YmU0NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5Y2NcdWQwN2MgXHViMmE1XHViODI1XHVjNzc0IFx1ZDVhNVx1YzBjMVx1YjQxY1x1YjJlNC4gXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjYzI5XHVjNmE5XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYzk0XHVjOGZjXHViOWM4XHViMmU0IFx1YjNjNVx1YjliZFx1YzgwMVx1YzczY1x1Yjg1YyBcdWIyYTVcdWI4MjVcdWM3NzQgXHVkNWE1XHVjMGMxXHViNDE4XHViYTcwLCBcdWNjMjlcdWM2YTlcdWQ1NWMgXHVjN2E1XHVjZTU4XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTJcdWI5Y2NcdWQwN2MgXHViMmE1XHViODI1XHVjNzc0IFx1ZDVhNVx1YzBjMVx1YjQxY1x1YjJlNC4gXHVjNWQwXHViOTdjIFx1YjRlNFx1YzViNCwgXHVjN2E1XHViZTQ0IGFcdWM2NDAgYlx1Yzc1OCBcdWMyZGNcdWI4MjUgXHVkNWE1XHVjMGMxIFx1YzgxMFx1YzIxOFx1YWMwMCAxMFx1YWNmYyAxNVx1Yzc3Y1x1YjU0YywgXHViNDUwIFx1YzdhNVx1YmU0NFx1Yjk3YyBcdWNjMjlcdWM2YTlcdWQ1NThcdWJhNzQgXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc4IDE1XHViOWNjXHVkMDdjIFx1YzJkY1x1YjgyNVx1Yzc3NCBcdWQ1YTVcdWMwYzFcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMTggMTVcdWI5N2MgXHViYzk0XHVjOGZjXHVjNzU4IFx1ZDY1NVx1YzdhNSBcdWM4MTBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Yzc3NCBcdWM2MDhcdWM1ZDBcdWMxMWMge2EsIGJ9XHVjNzU4IFx1YzJkY1x1YjgyNSBcdWQ1YTVcdWMwYzEgXHVkNjU1XHVjN2E1IFx1YzgxMFx1YzIxOFx1YjI5NCAxNVx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPktEU0lcdWIyOTQgXHVhZDcwXHVjNzc4IFx1ZDU1YyBcdWJhODVcdWM3NzQgXHVjN2E1XHViZTQ0XHViOTdjIEtcdWFjMWMgXHVjYzI5XHVjNmE5XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YjJhNVx1YjgyNSBcdWQ1YTVcdWMwYzFcdWM3NzQgXHViOWNlXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWM4NzBcdWQ1NjlcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkMmI5XHVjMjE4IFx1YmFhOVx1YzgwMSBcdWFkNzBcdWM3NzhcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1ZDJiOVx1YzgxNSBcdWJjOTRcdWM4ZmNcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1ZDZlOFx1YzUyYyBcdWIzNTQgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmM5NFx1YzZhOVx1YzEzMVx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVhYzAxIFx1YmM5NFx1YzhmY1x1Yzc1OCBcdWQ2NTVcdWM3YTUgXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDBcdWI0MThcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIE5cdWFjMWNcdWM3NTggXHVjN2E1XHViZTQ0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWQ2NTVcdWM3YTUgXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YzdhNVx1YmU0NCBLXHVhYzFjIFx1Yzg3MFx1ZDU2OVx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjN2E1XHViZTQ0XHVhYzAwIE5cdWFjMWNcdWI5N2MgezEsIC4uLiwgTn1cdWI4NWMsIFx1YWMwMSBcdWM3YTVcdWJlNDRcdWM3NTggXHVjODEwXHVjMjE4IFI8c3ViPmk8XC9zdWI+XHViOTdjIFx1YjJlNFx1YzEyZiBcdWM4MTVcdWMyMTggUjxzdWI+aTxcL3N1Yj4gPSAocjxzdWI+aSwxPFwvc3ViPiwgcjxzdWI+aSwyPFwvc3ViPiwgcjxzdWI+aSwzPFwvc3ViPiwgcjxzdWI+aSw0PFwvc3ViPiwgcjxzdWI+aSw1PFwvc3ViPikgKFx1YmFhOFx1YjRlMCBpPTEsLi4uLE5cdWFjZmMgaj0xLC4uLiw1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAwICZsZTsgcjxzdWI+aSxqPFwvc3ViPiAmbGU7IDEwLDAwMClcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIEsgKDEgJmxlOyBLICZsZTsgTilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNjU1XHVjN2E1IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM3YTVcdWJlNDQgS1x1YWMxY1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBOPTQsIEs9Mlx1Yzc3NFx1YWNlMCwgUmlcdWFjMDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlI8c3ViPjE8XC9zdWI+ID0gKDMwLCAzMCwgMzAsIDMwLCAwKTxcL2xpPlxyXG5cdDxsaT5SPHN1Yj4yPFwvc3ViPiA9ICg1MCwgMCwgMCwgMCwgMCk8XC9saT5cclxuXHQ8bGk+UjxzdWI+MzxcL3N1Yj4gPSAoMCwgNTAsIDAsIDUwLCAxMCk8XC9saT5cclxuXHQ8bGk+UjxzdWI+NDxcL3N1Yj4gPSAoMCwgMCwgNTAsIDAsIDIwKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlI8c3ViPjE8XC9zdWI+XHVhY2ZjIFI8c3ViPjM8XC9zdWI+XHVjNzQ0IFx1Y2MyOVx1YzZhOVx1ZDU1OFx1YmE3NCBcdWQ1YTVcdWMwYzEgXHVjODEwXHVjMjE4XHViMjk0IDMwKzUwKzMwKzUwKzEwID0gMTcwXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVjNzc0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhYzEyIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAsMDAwLCAxICZsZTsgSyAmbGU7IE4pIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWIyZTRcdWMxMmZcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IFx1YWMwMSBcdWM3YTVcdWJlNDRcdWM3NTggXHVjODEwXHVjMjE4IHI8c3ViPmksMTxcL3N1Yj4sIHI8c3ViPmksMjxcL3N1Yj4sIHI8c3ViPmksMzxcL3N1Yj4sIHI8c3ViPmksNDxcL3N1Yj4sIHI8c3ViPmksNTxcL3N1Yj5cdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YzgxNVx1YzIxOCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjN2E1XHViZTQ0IE5cdWFjMWNcdWM5MTEgS1x1YWMxY1x1Yjk3YyBcdWNjMjlcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDVhNVx1YzBjMSBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXF1aXBtZW50IiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgS29yZWEgRGVmZW5zZSBhbmQgU2NpZW5jZSBJbnN0aXR1dGUsIHNob3J0bHkgS0RTSSwgaGFzIGJlZW4gcHV0dGluZyBjb25zdGFudCBlZmZvcnQgaW50byBuZXcgZXF1aXBtZW50IGZvciBpbmRpdmlkdWFsIHNvbGRpZXJzIGZvciByZWNlbnQgeWVhcnMsIGFuZCBhdCBsYXN0IHJlbGVhc2VkIE4gbmV3IHR5cGVzIG9mIGVxdWlwbWVudC4gS0RTSSBoYXMgYWxyZWFkeSBkb25lIGV2YWx1YXRpb24gb2YgZWFjaCBvZiB0aGUgTiB0eXBlcyBvZiBlcXVpcG1lbnQsIGZpbmFsbHkgcmVzdWx0aW5nIGluIHNjb3JlcyBpbiBmaXZlIGNhdGVnb3JpZXM6IGF0dGFjayBpbXByb3ZlbWVudCwgZGVmZW5zZSBpbXByb3ZlbWVudCwgdmlzaW9uIGltcHJvdmVtZW50LCBwb3J0YWJpbGl0eSwgYW5kIGVhc2luZXNzIG9mIHVzYWdlLiBUaGUgc2NvcmUgaW4gZWFjaCBjYXRlZ29yeSBpcyBxdWFudGlmaWVkIGFzIGFuIGludGVnZXIgaW4gdGhlIHJhbmdlIDAgdG8gMTAsMDAwLCBhbmQgdGhlIHJhdGluZyBvZiBlYWNoIHR5cGUgb2YgZXF1aXBtZW50IGlzIHRodXMgcmVwcmVzZW50ZWQgYXMgYSBzZXF1ZW5jZSBvZiBmaXZlIGludGVnZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBjb25zaWRlcmF0aW9uIG9mIGNvc3RzIGFuZCBjYXBhYmlsaXR5IG9mIGF2ZXJhZ2UgaW5kaXZpZHVhbCBzb2xkaWVycywgS0RTSSBhbHNvIHJlcG9ydGVkIHRoYXQgZWFjaCBzb2xkaWVyIHdpbGwgYmUgYWJsZSB0byBpbnN0YWxsIGF0IG1vc3QgSyB0eXBlcyBvZiBlcXVpcG1lbnQgb24gaGlzIGJvZHkgdG8gZXh0ZW5kIGhpcyBhYmlsaXR5LiBJZiBhIHNpbmdsZSB0eXBlIGlzIGluc3RhbGxlZCBvbiBhIHNvbGRpZXIsIHRoZW4gaGlzIGFiaWxpdHkgaW4gZWFjaCBjYXRlZ29yeSBpcyBleHRlbmRlZCBieSB0aGUgc3BlY2lmaWVkIHNjb3JlIG9mIHRoYXQgdHlwZS4gTW9yZW92ZXIsIGlmIGEgc29sZGllciBpbnN0YWxscyBtb3JlIHRoYW4gb25lIHR5cGUgb2YgZXF1aXBtZW50LCB0aGVuIGhpcyBhYmlsaXR5IGluIGVhY2ggY2F0ZWdvcnkgaXMgZXh0ZW5kZWQgYnkgdGhlIG1heGltdW0gc2NvcmUgb2YgdGhlIGNob3NlbiB0eXBlcyBpbiB0aGF0IGNhdGVnb3J5LiBGb3IgZXhhbXBsZSwgaWYgdGhlIHZpc2lvbiBpbXByb3ZlbWVudCBzY29yZXMgb2YgdHlwZSBhIGFuZCB0eXBlIGIgYXJlIDEwIGFuZCAxNSwgcmVzcGVjdGl2ZWx5LCB0aGVuIGluc3RhbGxpbmcgYSBjb21iaW5hdGlvbiBvZiB0d28gdHlwZXMgYSBhbmQgYiB3aWxsIHJlc3VsdCBpbiBhIHZpc2lvbiBpbXByb3ZlbWVudCBieSB0aGVpciBtYXhpbXVtIHNjb3JlIDE1LiBXZSBjYWxsIHRoZSBtYXhpbXVtIHNjb3JlIDE1IHRoZSBleHRlbnNpb24gc2NvcmUgb2YgYSBjYXRlZ29yeTsgc28sIHRoZSBleHRlbnNpb24gc2NvcmUgb2YgdmlzaW9uIGltcHJvdmVtZW50IGZvciBjb21iaW5hdGlvbiB7YSwgYn0gaXMgMTUgaW4gdGhpcyBleGFtcGxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5LRFNJIG5vdyBzdGFydGVkIGRldmlzaW5nIGEgd2F5IG9mIGZpbmRpbmcgYW4gb3B0aW1hbCBjb21iaW5hdGlvbiBvZiBLIHR5cGVzIG9mIGVxdWlwbWVudCBmb3IgYmVzdCBwZXJmb3JtYW5jZSBvZiBpbmRpdmlkdWFsIHNvbGRpZXJzLiBXaGlsZSBhIGZvcmNlIGNhbiBzb21ldGltZXMgYmUgb2YgYSBzcGVjaWFsIHB1cnBvc2Ugc28gdGhhdCBhIGNlcnRhaW4gY2F0ZWdvcnkgd291bGQgYmUgbW9yZSBpbXBvcnRhbnQgdGhhbiB0aGUgb3RoZXJzLCBldmVyeSBzaW5nbGUgY2F0ZWdvcnkgaXMsIGhvd2V2ZXIsIHJlZ2FyZGVkIGVxdWFsbHkgaW1wb3J0YW50IGluIGdlbmVyYWwuIEZvciB0aGlzIGdlbmVyYWwgcHVycG9zZSwgS0RTSSBkZWZpbmVkIHRoZSBvYmplY3RpdmUgc2NvcmUgb2YgYSBjb21iaW5hdGlvbiBvZiBlcXVpcG1lbnQgdG8gYmUgdGhlIHN1bSBvZiB0aGUgZXh0ZW5zaW9uIHNjb3JlcyBvZiB0aGUgZml2ZSBjYXRlZ29yaWVzIGZvciB0aGUgY29tYmluYXRpb24uIEtEU0kgdGh1cyB3YW50cyB0byBmaW5kIGEgYmVzdCBjb21iaW5hdGlvbiBvZiBLIHR5cGVzIG9mIGVxdWlwbWVudCBzdWNoIHRoYXQgaXRzIG9iamVjdGl2ZSBzY29yZSBpcyBtYXhpbWl6ZWQgYW1vbmcgYWxsIHBvc3NpYmxlIGNvbWJpbmF0aW9ucyBvZiBLIHR5cGVzLiBZb3UgYXJlIGFza2VkIGJ5IEtEU0kgdG8gZGV2aXNlIGFuZCB3cml0ZSBhIGNvbXB1dGVyIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgb2JqZWN0aXZlIHNjb3JlIG9mIGEgYmVzdCBjb21iaW5hdGlvbiBvZiBLIHR5cGVzIG9mIGVxdWlwbWVudCwgdGhhdCBpcywgdGhlIG1heGltdW0gcG9zc2libGUgb2JqZWN0aXZlIHNjb3JlIGZvciBhbGwgcG9zc2libGUgY29tYmluYXRpb25zIG9mIEsgdHlwZXMgYW1vbmcgdGhlIGdpdmVuIE4gdHlwZXMgb2YgZXF1aXBtZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5QdXQgZGlmZmVyZW50bHksIHlvdSBhcmUgZ2l2ZW4gTiB0eXBlcyBvZiBlcXVpcG1lbnQgezEsIC4uLiwgTn0gYW5kIHRoZWlyIHJhdGluZ3MgUjxzdWI+aTxcL3N1Yj4gcmVwcmVzZW50ZWQgYnkgZml2ZSBpbnRlZ2VycyBSPHN1Yj5pPFwvc3ViPiA9IChyPHN1Yj5pLDE8XC9zdWI+LCByPHN1Yj5pLDI8XC9zdWI+LCByPHN1Yj5pLDM8XC9zdWI+LCByPHN1Yj5pLDQ8XC9zdWI+LCByPHN1Yj5pLDU8XC9zdWI+KSB3aXRoIDAgJmxlOyByPHN1Yj5pLGo8XC9zdWI+ICZsZTsgMTAsMDAwIGZvciBlYWNoIGksIC4uLiwgTiBhbmQgaiA9IDEsIC4uLiwgNS4gR2l2ZW4gYW5vdGhlciBuYXR1cmFsIG51bWJlciBLICgxICZsZTsgSyAmbGU7IE4pLCB5b3VyIHByb2dyYW0gaGFzIHRvIGNvbXB1dGUgdGhlIG9iamVjdGl2ZSBzY29yZSBvZiBhIGJlc3QgY29tYmluYXRpb24gb2YgSyB0eXBlcyBvZiBlcXVpcG1lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciBhbiBpbnB1dCBpbnN0YW5jZSBpbiB3aGljaCBOID0gNCwgSyA9IDIsIGFuZCBlYWNoIFI8c3ViPmk8XC9zdWI+IGlzIGdpdmVuIGFzIGJlbG93OiZuYnNwOzxcL3A+XHJcblxyXG48cD5SPHN1Yj4xPFwvc3ViPiA9ICgzMCwgMzAsIDMwLCAzMCwgMCkmbmJzcDs8YnIgXC8+XHJcblI8c3ViPjI8XC9zdWI+ID0gKDUwLCAwLCAwLCAwLCAwKSZuYnNwOzxiciBcLz5cclxuUjxzdWI+MzxcL3N1Yj4gPSAoMCwgNTAsIDAsIDUwLCAxMCkmbmJzcDs8YnIgXC8+XHJcblI8c3ViPjQ8XC9zdWI+ID0gKDAsIDAsIDUwLCAwLCAyMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZW4sIGNob29zaW5nIFI8c3ViPjE8XC9zdWI+IGFuZCBSPHN1Yj4zPFwvc3ViPiBmb3JtcyBhIGJlc3QgY29tYmluYXRpb24gb2YgdHdvIHR5cGVzIHsxLCAzfSBhbmQgeWllbGRzIHRoZSBvYmplY3RpdmUgc2NvcmUgMzArNTArMzArNTArMTAgPSAxNzAsIHdoaWNoIHdpbGwgYmUgdGhlIGFuc3dlciBvZiBhIGNvcnJlY3QgcHJvZ3JhbS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgVCBvZiB0ZXN0IGNhc2VzIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRnJvbSB0aGUgc2Vjb25kIGxpbmUsIGVhY2ggdGVzdCBjYXNlIGlzIGdpdmVuIGluIG9yZGVyLCBjb25zaXN0aW5nIG9mIHRoZSBmb2xsb3dpbmc6IGEgdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDEwLDAwMCkgYW5kIEsgKDEgJmxlOyBLICZsZTsgTikgaW4gaXRzIGZpcnN0IGxpbmUsIGFuZCBpcyBmb2xsb3dlZCBieSBOIGxpbmVzIGVhY2ggb2Ygd2hpY2ggY29uc2lzdHMgb2YgZml2ZSBpbnRlZ2VycyBpbmNsdXNpdmVseSBiZXR3ZWVuIDAgYW5kIDEwLDAwMCwgcmVwcmVzZW50aW5nIHRoZSBmaXZlIHNjb3JlcyByPHN1Yj5pLDE8XC9zdWI+LCByPHN1Yj5pLDI8XC9zdWI+LCByPHN1Yj5pLDM8XC9zdWI+LCByPHN1Yj5pLDQ8XC9zdWI+LCBhbmQgcjxzdWI+aSw1PFwvc3ViPiBvZiBlYWNoIHR5cGUgaSBvZiBlcXVpcG1lbnQgZm9yIGkgPSAxLCAuLi4sIE4gaW4gb3JkZXIuIFR3byBjb25zZWN1dGl2ZSBpbnRlZ2VycyBpbiBvbmUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlIGFuZCB0aGVyZSBpcyBubyBlbXB0eSBsaW5lIGJldHdlZW4gdHdvIGNvbnNlY3V0aXZlIHRlc3QgY2FzZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgb2JqZWN0aXZlIHNjb3JlIG9mIGEgYmVzdCBjb21iaW5hdGlvbiBvZiBLIHR5cGVzIG9mIGVxdWlwbWVudDsgdGhlIG1heGltdW0gcG9zc2libGUgb2JqZWN0aXZlIHNjb3JlIGZvciBhbGwgcG9zc2libGUgY29tYmluYXRpb25zIG9mIEsgdHlwZXMgYW1vbmcgdGhlIGdpdmVuIE4gdHlwZXMgb2YgZXF1aXBtZW50IGZvciB0aGUgY29ycmVzcG9uZGluZyB0ZXN0IGNhc2UuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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