시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 86 47 37 57.812%

문제

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+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YWNmNVx1Yzc3NCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YzMxM1x1YzVlY1x1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWFjZjVcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFx1YWMxMlx1Yzc3NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWQ1NWMgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RzdGFjay5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzZweDsgd2lkdGg6MTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YWNmNVx1Yzc0NCBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhY2UwXHViOTc4IFx1YWNmNVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhY2Y1XHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YmE3NCwgXHVhZGY4IFx1YWNmNVx1Yzc0MCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHViNDFjXHViMmU0LiBcdWM4MTBcdWMyMThcdWFjMDAgXHViMTkyXHVjNzQ0XHVjMjE4XHViODVkIFx1Yzg4Ylx1Yzc0MCBcdWMwYzFcdWQ0ODhcdWM3NDQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNjMzhcdWFjMDBcdWM3OTBcdWIyOTQgXHVhZGY4IFx1YWNmNVx1Yzc1OCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNmNVx1Yzc0NCBcdWFjZTBcdWI5NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1YWRmOCZuYnNwO1x1YWNmNVx1Yzc0NCZuYnNwO1x1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCBcdWFjZjVcdWM3NDQgXHVhY2UwXHViOTdjIFx1YWM4M1x1Yzc3OFx1YzljMCwgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzkxMVx1YjJlOFx1ZDU2MCBcdWFjODNcdWM3NzhcdWM5YzAgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhY2Y1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWFjZTBcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4MTBcdWMyMThcdWIyOTQgMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBQRCBcdWFlNDBcdWIzZDlcdWFkZGNcdWIyOTQgXHVjYzM4XHVhYzAwXHVjNzkwXHViNGU0XHVjNzc0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0MCBcdWJhODcgXHVjODEwXHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1ZDU4OVx1YzczY1x1Yjg1YyBcdWMzMTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0XHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0NCBOXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2QxZCBpXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBCPHN1Yj5pajxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwPHN1cD41PFwvc3VwPiAmbGU7IEI8c3ViPmlqPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiwgMSAmbGU7IGogJmxlOyBpICZsZTsgTikgQmlqXHViMjk0IGlcdWQ1ODkgalx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiAoXHVjY2FiIFx1ZDU4OVx1Yzc0MCBcdWFjMDBcdWM3YTUgXHVjNzE3IFx1ZDU4OSwgXHVhYzAxIFx1ZDU4OVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWNmNVx1Yzc0MCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YWNmNSk8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjYzM4XHVhYzAwXHVjNzkwXHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU2ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWxsIFN0YWNraW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgWFlaIFRWIGNoYW5uZWwgaXMgZGV2ZWxvcGluZyBhIG5ldyBnYW1lIHNob3csIHdoZXJlIGEgY29udGVzdGFudCBoYXMgdG8gbWFrZSBzb21lIGNob2ljZXMgaW4gb3JkZXIgdG8gZ2V0IGEgcHJpemUuIFRoZSBnYW1lIGNvbnNpc3RzIG9mIGEgdHJpYW5ndWxhciBzdGFjayBvZiBiYWxscywgZWFjaCBvZiB0aGVtIGhhdmluZyBhbiBpbnRlZ2VyIHZhbHVlLCBhcyB0aGUgZm9sbG93aW5nIGV4YW1wbGUgc2hvd3MuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHN0YWNrLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzNnB4OyB3aWR0aDoxNzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgY29udGVzdGFudCBtdXN0IGNob29zZSB3aGljaCBiYWxscyBoZSBpcyBnb2luZyB0byB0YWtlIGFuZCBoaXMgcHJpemUgaXMgdGhlIHN1bSBvZiB0aGUgdmFsdWVzIG9mIHRob3NlIGJhbGxzLiBIb3dldmVyLCB0aGUgY29udGVzdGFudCBjYW4gdGFrZSBhbnkgZ2l2ZW4gYmFsbCBvbmx5IGlmIGhlIGFsc28gdGFrZXMgdGhlIGJhbGxzIGRpcmVjdGx5IG9uIHRvcCBvZiBpdC4gVGhpcyBtYXkgcmVxdWlyZSB0YWtpbmcgYWRkaXRpb25hbCBiYWxscyB1c2luZyB0aGUgc2FtZSBydWxlLiBOb3RpY2UgdGhhdCB0aGUgY29udGVzdGFudCBtYXkgY2hvb3NlIG5vdCB0byB0YWtlIGFueSBiYWxsLCBpbiB3aGljaCBjYXNlIHRoZSBwcml6ZSBpcyB6ZXJvLjxcL3A+XHJcblxyXG48cD5UaGUgVFYgc2hvdyBkaXJlY3RvciBpcyBjb25jZXJuZWQgYWJvdXQgdGhlIG1heGltdW0gcHJpemUgYSBjb250ZXN0YW50IGNhbiBtYWtlIGZvciBhIGdpdmVuIHN0YWNrLiBTaW5jZSBoZSBpcyB5b3VyIGJvc3MgYW5kIGhlIGRvZXMgbm90IGtub3cgaG93IHRvIGFuc3dlciB0aGlzIHF1ZXN0aW9uLCBoZSBhc3NpZ25lZCB0aGlzIHRhc2sgdG8geW91LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIHVzaW5nIHNldmVyYWwgbGluZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygcm93cyBvZiB0aGUgc3RhY2sgKDEgJmxlOyBOICZsZTsgMTAwMCkuIFRoZSBpLXRoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgaSBpbnRlZ2VycyBCPHN1Yj5pajxcL3N1Yj4gKCZtaW51czsxMDxzdXA+NTxcL3N1cD4gJmxlOyBCPHN1Yj5pajxcL3N1Yj4gJmxlOyAxMDxzdXA+NTxcL3N1cD4gZm9yIDEgJmxlOyBqICZsZTsgaSAmbGU7IE4pOyB0aGUgbnVtYmVyIEJpaiBpcyB0aGUgdmFsdWUgb2YgdGhlIGotdGggYmFsbCBpbiB0aGUgaS10aCByb3cgb2YgdGhlIHN0YWNrICh0aGUgXHVmYjAxcnN0IHJvdyBpcyB0aGUgdG9wbW9zdCBvbmUsIGFuZCB3aXRoaW4gZWFjaCByb3cgdGhlIFx1ZmIwMXJzdCBiYWxsIGlmIHRoZSBsZWZ0bW9zdCBvbmUpLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCB0ZXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25lIHplcm8uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBhIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbWF4aW11bSBwcml6ZSBhIGNvbnRlc3RhbnQgY2FuIG1ha2UgZnJvbSB0aGUgc3RhY2suPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d