시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB72805342972428046.830%

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력 1

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력 1

260
290
W3sicHJvYmxlbV9pZCI6Ijk0NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQyZjBcdWNlZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM1ZWNcdWIzZDlcdWMwZGQgXHVjMGMxXHViMGU1XHVjNzc0XHViMjk0IFx1YmIzOFx1YmMyOVx1YWQ2Y1x1YzVkMFx1YzExYyBcdWMyYTRcdWQyZjBcdWNlZTQgMm5cdWFjMWNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWMyYTRcdWQyZjBcdWNlZTRcdWIyOTQgXHVhZGY4XHViOWJjIChhKVx1YzY0MCBcdWFjMTlcdWM3NzQgMlx1ZDU4OSBuXHVjNWY0XHViODVjIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YjBlNVx1Yzc3NFx1YjI5NCBcdWMyYTRcdWQyZjBcdWNlZTRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Y2M0NVx1YzBjMVx1Yzc0NCBcdWFmYjhcdWJiZjhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWIwZTVcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTVjIFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWQ0ODhcdWM5YzhcdWM3NDAgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YzJhNFx1ZDJmMFx1Y2VlNCBcdWQ1NWMgXHVjN2E1XHVjNzQ0IFx1YjViY1x1YmE3NCwgXHVhZGY4IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1YzY0MCBcdWJjYzBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHViMjk0IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjYzIyXHVjNWI0XHVjODM4XHVjMTFjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWI1YzAgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM3MDQsIFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMmYwXHVjZWU0XHViMjk0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdGlja2VyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1MHB4OyB3aWR0aDo1NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjMmE0XHVkMmYwXHVjZWU0XHViOTdjIFx1YmQ5OVx1Yzc3YyBcdWMyMTggXHVjNWM2XHVhYzhjXHViNDFjIFx1YzBjMVx1YjBlNVx1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNWQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWI5ZTRcdWFlMzBcdWFjZTAsIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWMyYTRcdWQyZjBcdWNlZTRcdWI5N2MgXHViNWJjXHVjNWI0XHViMGI0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWFkZjhcdWI5YmMgKGIpXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjMDEgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNWQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWI5ZTRcdWFjYmNcdWIyZTQuIFx1YzBjMVx1YjBlNVx1Yzc3NFx1YWMwMCBcdWI1YzQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWQyZjBcdWNlZTRcdWM3NTggXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjOTg5LCAyblx1YWMxY1x1Yzc1OCBcdWMyYTRcdWQyZjBcdWNlZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YmE3NFx1YzExYyBcdWMxMWNcdWI4NWMgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMCBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzJhNFx1ZDJmMFx1Y2VlNCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODEwXHVjMjE4XHVhYzAwIDUwLCA1MCwgMTAwLCA2MFx1Yzc3OCBcdWMyYTRcdWQyZjBcdWNlZTRcdWI5N2MgXHVhY2UwXHViOTc0XHViYTc0LCBcdWM4MTBcdWMyMThcdWIyOTQgMjYwXHVjNzc0IFx1YjQxOFx1YWNlMCBcdWM3NzQgXHVhYzgzXHVjNzc0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWI0NTAgXHVjMmE0XHVkMmYwXHVjZWU0ICgxMDBcdWFjZmMgNzApXHVjNzQwIFx1YmNjMFx1Yzc0NCBcdWFjZjVcdWM3MjBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViNWM0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG4gKDEgJmxlOyBuICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHViNDUwIFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgXHVhZGY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNWYwXHVjMThkXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YjJlNC4gXHVjODEwXHVjMjE4XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgMm5cdWFjMWNcdWM3NTggXHVjMmE0XHVkMmYwXHVjZWU0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWI0NTAgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMmE0XHVkMmYwXHVjZWU0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk0NjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdGlja2VycyIsImRlc2NyaXB0aW9uIjoiPHA+TmFuY3ksIHlvdXIgbGl0dGxlIHNpc3RlciwgaGFzIGEgc2hlZXQgb2YgMm4gc3RpY2tlcnMgb2YgcmVjdGFuZ3VsYXIgc2hhcGUgdGhhdCBhcmUgYXJyYW5nZWQgaW4gMiByb3dzIGFuZCBuIGNvbHVtbnMuIFNlZSBGaWd1cmUgMShhKS4gTmFuY3kgd2FudHMgdG8gZGVjb3JhdGUgaGVyIGRlc2sgd2l0aCB0aGUgc3RpY2tlcnMuIEJ1dCB0aGUgcXVhbGl0eSBvZiB0aGUgc3RpY2tlcnMgaXMgcG9vciwgYW5kIHRlYXJpbmcgb2ZmIG9uZSBzdGlja2VyIGZyb20gdGhlIHNoZWV0IHNwb2lscyB0aGUgc3RpY2tlcnMgc2hhcmluZyBhbiBlZGdlIHdpdGggaXQuIFNvLCBOYW5jeSBtdXN0IGxvc2UgdGhlIHN0aWNrZXJzIGFib3ZlLCBiZWxvdywgdG8gdGhlIGxlZnQgb2YsIGFuZCB0byB0aGUgcmlnaHQgb2YgdGhlIHN0aWNrZXIgc2hlIHRlYXJzIG9mZi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdGlja2VyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1MHB4OyB3aWR0aDo1NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gQSBzaGVldCBvZiAxMCBzdGlja2VycyBpbiAyIHJvd3MmbmJzcDs8XC9wPlxyXG5cclxuPHA+TmFuY3kgaGFkIG5vIGlkZWEgYWJvdXQgd2hhdCB0byBkby4gWW91IGxvb2tlZCBhdCBoZXIgYW5kIHN1Z2dlc3RlZCB0aGF0IHNoZSBzaG91bGQgc2NvcmUgZWFjaCBzdGlja2VyIGFuZCB0cnkgdG8gY2hvb3NlIGEgcG9zc2libGUgc2V0IG9mIHN0aWNrZXJzIHRoYXQgbWF4aW1pemVzIHRoZSB0b3RhbCBzY29yZS4gTmFuY3kgbWFya2VkIHNjb3JlcyB0byBhbGwgdGhlIDJuIHN0aWNrZXJzIGFzIGluIEZpZ3VyZSAxKGIpLiBBbmQgTmFuY3kgaGFkIG5vIGlkZWEsIGFnYWluLiBZb3UgYWdhaW4gdG9vayBhIGxvb2sgYXQgaGVyIGFuZCBzaWdoZWQuIFlvdSBjYW5ub3QgaGVscCBkb2luZyBzb21ldGhpbmcgZm9yIGhlciwgYW5kIGF0IGxhc3QgZGVjaWRlZCB0byBoZWxwIGhlciB3aXRoIGEgZmFzdCBjb21wdXRlciBwcm9ncmFtLiBZb3VyIHByb2dyYW0gaXMgdG8gc2VsZWN0IGEgc2V0IG9mIHN0aWNrZXJzIG9mIG1heGltdW0gdG90YWwgc2NvcmUgZnJvbSB0aGUgMm4gc3RpY2tlcnMgc3VjaCB0aGF0IG5vIHR3byBvZiB0aGVtIHNoYXJlIGFuIGVkZ2UuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBleGFtcGxlIHNob3duIGluIEZpZ3VyZSAxLCB0aGUgbWF4aW11bSB0b3RhbCBzY29yZSBpcyAyNjAgd2hlbiB5b3Ugc2VsZWN0IHRoZSBmb3VyIHN0aWNrZXJzIG9mIHNjb3JlcyA1MCwgNTAsIDEwMCwgNjAuIFVuZm9ydHVuYXRlbHksIGluIHRoaXMgY2FzZSwgaXQgaXMgbm90IGFsbG93ZWQgdG8gc2ltdWx0YW5lb3VzbHkgc2VsZWN0IGJvdGggb2YgdGhlIHR3byBoaWdoZXN0IHNjb3JlZCBzdGlja2VycyAob2Ygc2NvcmUgMTAwIGFuZCA3MCkgYmVjYXVzZSB0aGUgdHdvIHN0aWNrZXJzIHNoYXJlIGFuIGVkZ2UgYmV0d2VlbiB0aGVtLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgdGhhdCBjb250YWlucyBhbiBpbnRlZ2VyICgxICZsZTsgbiAmbGU7IDEwMCwwMDApLCB3aGVyZSAybiBpcyB0aGUgbnVtYmVyIG9mIHN0aWNrZXJzIGluIHRoZSBzaGVldC4gSW4gdGhlIG5leHQgdHdvIGxpbmVzLCBlYWNoIGxpbmUgY29udGFpbnMgbiBpbnRlZ2VycywgZWFjaCBvZiB3aGljaCByZXByZXNlbnRzIE5hbmN5JnJzcXVvO3Mgc2NvcmUgZm9yIHRoZSBzdGlja2VyIGF0IHRoYXQgcG9zaXRpb24gaW4gdGhlIHN0aWNrZXIgc2hlZXQuIEV2ZXJ5IHR3byBjb25zZWN1dGl2ZSBpbnRlZ2VycyBpbiBhIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIGJsYW5rLiBOb3RlIHRoYXQgdGhlIDJuIHN0aWNrZXJzIGFyZSBvZiByZWN0YW5ndWxhciBzaGFwZSBhbmQgYXJlIGFycmFuZ2VkIGluIDIgcm93cyBhbmQgbiBjb2x1bW5zIGluIHRoZSBzaGVldC4gTmFuY3kmcnNxdW87cyBzY29yZXMgcmFuZ2UgZnJvbSAwIHRvIDEwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG1heGltdW0gcG9zc2libGUgdG90YWwgc2NvcmUgZm9yIGEgc3Vic2V0IG9mIHRoZSAybiBzdGlja2VycyBzdWNoIHRoYXQgbm8gdHdvIHN0aWNrZXJzIHNoYXJlIGFuIGVkZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2013 K번