시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 80 44 34 58.621%

문제

KDK방송국은 새로운 게임 쇼를 하나 만들었다. 참가자는 선택을 몇 개 하게 되고, 이 선택에 따라서 상품을 얻게 된다.

먼저, 공이 삼각형 모양으로 쌓여져 있고, 각 공에는 정수 값이 하나씩 써 있다. 아래 그림은 한 예이다.

참가자는 공을 고를 수 있고, 고른 공에 써있는 숫자의 합이 점수가 된다. 공을 고르면, 그 공은 삼각형에서 제거된다. 점수가 높을수록 좋은 상품을 받게 된다. 하지만, 참가자는 그 공의 위에 있는 공을 고른 경우에만 그 공을 고를 수 있다. 또, 참가자는 공을 고를 것인지, 게임을 중단할 것인지 선택할 수 있다. 만약, 공을 하나도 고르지 않은 경우에 점수는 0이 된다.

프로그램 PD 김동규는 참가자들이 얻을 수 있는 점수의 최대값을 구해보려고 한다. 점수의 최대값은 몇 점일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 공이 총 몇 행으로 쌓여져 있는지가 주어진다. 이 값을 N이라고 한다. (1 ≤ N ≤ 1000) 다음 N개의 줄의 i번째 줄에는 총 i개의 정수 Bij가 주어진다. (-105 ≤ Bij ≤ 105, 1 ≤ j ≤ i ≤ N) Bij는 i행 j열에 있는 공에 써 있는 정수이다. (첫 행은 가장 윗 행, 각 행의 첫번째 공은 가장 왼쪽 공)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 참가자가 얻을 수 있는 점수의 최대값을 출력한다.

예제 입력 1

4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0

예제 출력 1

7
0
6
W3sicHJvYmxlbV9pZCI6IjU2ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5LREtcdWJjMjlcdWMxYTFcdWFkNmRcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YWM4Y1x1Yzc4NCBcdWMxZmNcdWI5N2MgXHVkNTU4XHViMDk4IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YzEyMFx1ZDBkZFx1Yzc0NCBcdWJhODcgXHVhYzFjIFx1ZDU1OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1Yzc3NCBcdWMxMjBcdWQwZGRcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YzBjMVx1ZDQ4OFx1Yzc0NCBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YWNmNVx1Yzc3NCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YzMxM1x1YzVlY1x1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWFjZjVcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFx1YWMxMlx1Yzc3NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMzY4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWQ1NWMgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RzdGFjay5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzZweDsgd2lkdGg6MTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YWNmNVx1Yzc0NCBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhY2UwXHViOTc4IFx1YWNmNVx1YzVkMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFjZjVcdWM3NDQgXHVhY2UwXHViOTc0XHViYTc0LCBcdWFkZjggXHVhY2Y1XHVjNzQwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWI0MWNcdWIyZTQuIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWIxOTJcdWM3NDRcdWMyMThcdWI4NWQgXHVjODhiXHVjNzQwIFx1YzBjMVx1ZDQ4OFx1Yzc0NCBcdWJjMWJcdWFjOGMgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCBcdWFkZjggXHVhY2Y1XHVjNzU4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVjNzQ0IFx1YWNlMFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWI5Y2MgXHVhZGY4Jm5ic3A7XHVhY2Y1XHVjNzQ0Jm5ic3A7XHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YWNmNVx1Yzc0NCBcdWFjZTBcdWI5N2MgXHVhYzgzXHVjNzc4XHVjOWMwLCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOTExXHViMmU4XHVkNTYwIFx1YWM4M1x1Yzc3OFx1YzljMCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjZjVcdWM3NDQgXHVkNTU4XHViMDk4XHViM2M0IFx1YWNlMFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzgxMFx1YzIxOFx1YjI5NCAwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFBEIFx1YWU0MFx1YjNkOVx1YWRkY1x1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQwIFx1YmE4NyBcdWM4MTBcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVjNzc0IFx1Y2QxZCBcdWJhODcgXHVkNTg5XHVjNzNjXHViODVjIFx1YzMxM1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQ0IE5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDFkIGlcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEI8c3ViPmlqPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTA8c3VwPjU8XC9zdXA+ICZsZTsgQjxzdWI+aWo8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+LCAxICZsZTsgaiAmbGU7IGkgJmxlOyBOKSBCaWpcdWIyOTQgaVx1ZDU4OSBqXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIChcdWNjYWIgXHVkNTg5XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM3MTcgXHVkNTg5LCBcdWFjMDEgXHVkNTg5XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWFjZjVcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWFjZjUpPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsbCBTdGFja2luZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIFhZWiBUViBjaGFubmVsIGlzIGRldmVsb3BpbmcgYSBuZXcgZ2FtZSBzaG93LCB3aGVyZSBhIGNvbnRlc3RhbnQgaGFzIHRvIG1ha2Ugc29tZSBjaG9pY2VzIGluIG9yZGVyIHRvIGdldCBhIHByaXplLiBUaGUgZ2FtZSBjb25zaXN0cyBvZiBhIHRyaWFuZ3VsYXIgc3RhY2sgb2YgYmFsbHMsIGVhY2ggb2YgdGhlbSBoYXZpbmcgYW4gaW50ZWdlciB2YWx1ZSwgYXMgdGhlIGZvbGxvd2luZyBleGFtcGxlIHNob3dzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RzdGFjay5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzZweDsgd2lkdGg6MTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGNvbnRlc3RhbnQgbXVzdCBjaG9vc2Ugd2hpY2ggYmFsbHMgaGUgaXMgZ29pbmcgdG8gdGFrZSBhbmQgaGlzIHByaXplIGlzIHRoZSBzdW0gb2YgdGhlIHZhbHVlcyBvZiB0aG9zZSBiYWxscy4gSG93ZXZlciwgdGhlIGNvbnRlc3RhbnQgY2FuIHRha2UgYW55IGdpdmVuIGJhbGwgb25seSBpZiBoZSBhbHNvIHRha2VzIHRoZSBiYWxscyBkaXJlY3RseSBvbiB0b3Agb2YgaXQuIFRoaXMgbWF5IHJlcXVpcmUgdGFraW5nIGFkZGl0aW9uYWwgYmFsbHMgdXNpbmcgdGhlIHNhbWUgcnVsZS4gTm90aWNlIHRoYXQgdGhlIGNvbnRlc3RhbnQgbWF5IGNob29zZSBub3QgdG8gdGFrZSBhbnkgYmFsbCwgaW4gd2hpY2ggY2FzZSB0aGUgcHJpemUgaXMgemVyby48XC9wPlxyXG5cclxuPHA+VGhlIFRWIHNob3cgZGlyZWN0b3IgaXMgY29uY2VybmVkIGFib3V0IHRoZSBtYXhpbXVtIHByaXplIGEgY29udGVzdGFudCBjYW4gbWFrZSBmb3IgYSBnaXZlbiBzdGFjay4gU2luY2UgaGUgaXMgeW91ciBib3NzIGFuZCBoZSBkb2VzIG5vdCBrbm93IGhvdyB0byBhbnN3ZXIgdGhpcyBxdWVzdGlvbiwgaGUgYXNzaWduZWQgdGhpcyB0YXNrIHRvIHlvdS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIGlzIGRlc2NyaWJlZCB1c2luZyBzZXZlcmFsIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHJvd3Mgb2YgdGhlIHN0YWNrICgxICZsZTsgTiAmbGU7IDEwMDApLiBUaGUgaS10aCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGkgaW50ZWdlcnMgQjxzdWI+aWo8XC9zdWI+ICgmbWludXM7MTA8c3VwPjU8XC9zdXA+ICZsZTsgQjxzdWI+aWo8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+IGZvciAxICZsZTsgaiAmbGU7IGkgJmxlOyBOKTsgdGhlIG51bWJlciBCaWogaXMgdGhlIHZhbHVlIG9mIHRoZSBqLXRoIGJhbGwgaW4gdGhlIGktdGggcm93IG9mIHRoZSBzdGFjayAodGhlIFx1ZmIwMXJzdCByb3cgaXMgdGhlIHRvcG1vc3Qgb25lLCBhbmQgd2l0aGluIGVhY2ggcm93IHRoZSBcdWZiMDFyc3QgYmFsbCBpZiB0aGUgbGVmdG1vc3Qgb25lKS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIG9uZSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgYSBsaW5lIHdpdGggYW4gaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG1heGltdW0gcHJpemUgYSBjb250ZXN0YW50IGNhbiBtYWtlIGZyb20gdGhlIHN0YWNrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==