시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 86 15 13 28.889%

문제

오른쪽 삼각형은 9개의 단위 삼각형이 총 3줄(N=3)로 이루어져 있다. 단위 삼각형은 N=1인 삼각형이다.

이때, 그림에서 서로 다른 부분 삼각형은 총 13개가 있다. (N=1인 삼각형이 9개, N=2인 삼각형이 3개, N=3인 삼각형이 1개)

N = 1인 경우 부분 삼각형은 1개, 2인 경우에는 5개, 3인 경우는 13개, 4인 경우는 27개가 있다.

이때, 단위 삼각형의 값을 삼각형 내부에 쓰여 있는 숫자의 값이라고 하자. 삼각형의 값은 삼각형 안에 있는 단위 삼각형의 값의 합이다.

오른쪽 그림은 가장 큰 값을 갖는 부분 삼각형이다.

삼각형이 주어졌을 때, 가장 큰 값을 갖는 부분 삼각형을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 줄의 수를 나타내고, 다음 숫자는 단위 삼각형에 적혀있는 값이 위에서 아래, 왼쪽에서 오른쪽 순서대로 주어진다. 마지막 줄에는 0이 주어진다.

줄의 개수는 400을 넘지 않으며, 단위 삼각형에 적혀있는 값의 절댓값은 1000을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 테스트 케이스의 번호와 가장 큰 부분 삼각형의 값을 출력한다.

예제 입력 1

3 6 -24 0 12 -10 12 40 -4 6
4 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1
0

예제 출력 1

1. 54
2. 4
W3sicHJvYmxlbV9pZCI6IjQ5MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzBweDsgd2lkdGg6MTM0cHhcIiBcLz5cdWM2MjRcdWI5NzhcdWNhYmQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIDlcdWFjMWNcdWM3NTggXHViMmU4XHVjNzA0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWNkMWQgM1x1YzkwNChOPTMpXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDAgTj0xXHVjNzc4IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJkODBcdWJkODQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1Y2QxZCAxM1x1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIChOPTFcdWM3NzggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IDlcdWFjMWMsIE49Mlx1Yzc3OCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgM1x1YWMxYywgTj0zXHVjNzc4IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCAxXHVhYzFjKTxcL3A+XHJcblxyXG48cD5OID0gMVx1Yzc3OCBcdWFjYmRcdWM2YjAgXHViZDgwXHViZDg0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0MCAxXHVhYzFjLCAyXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCA1XHVhYzFjLCAzXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCAxM1x1YWMxYywgNFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgMjdcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVhYzEyXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM3MDQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxMlx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHIxLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMjZweDsgd2lkdGg6MTMzcHhcIiBcLz5cdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWJkODBcdWJkODQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjOTA0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YjJlNFx1Yzc0YyBcdWMyMmJcdWM3OTBcdWIyOTQgXHViMmU4XHVjNzA0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVhYzEyXHVjNzc0IFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTA0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA0MDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHViMmU4XHVjNzA0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc0MCAxMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YmQ4MFx1YmQ4NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWRkaW5nIHVwIFRyaWFuZ2xlcyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ci5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTMwcHg7IHdpZHRoOjEzNHB4XCIgXC8+VGFrZSBhIGxvb2sgYXQgdGhlIHRyaWFuZ2xlIG9uIHRoZSByaWdodC4gSXQgaXMgbWFkZSBvZiA5ICh1bml0KSB0cmlhbmdsZXMgYXJyYW5nZWQgaW4gdGhyZWUgcm93cyAoTj0zKS4gTmVlZGxlc3MgdG8gc2F5LCBhIHVuaXQgdHJpYW5nbGUgaXMgYSB0cmlhbmdsZSB3aXRoIE49MS4gSWYgeW91IHN0dWR5IHRoZSBcdWZiMDFndXJlIGZvciBmZXcgc2Vjb25kcywgeW91JnJzcXVvO2xsIHJlYWxpemUgdGhhdCB5b3UgY2FuIFx1ZmIwMW5kIDEzIGRpXHVmYjAwZXJlbnQgdHJpYW5nbGVzICh3aGljaCB3ZSZyc3F1bztsbCBjYWxsIHN1Yi10cmlhbmdsZXMuKSBPZiB0aGVzZSAxMyBzdWItdHJpYW5nbGVzIHdlIGhhdmU6IE5pbmUgdW5pdCB0cmlhbmdsZTsgdGhyZWUgd2l0aCBOPTIsIGFuZCBvbmUgd2l0aCBOPTMuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdGFibGUgbGlzdHMgdGhlIG51bWJlciBvZiBzdWItdHJpYW5nbGVzIGluIGFycmFuZ2VtZW50cyB3aXRoIE4gJmx0OyA1LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyMS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTI2cHg7IHdpZHRoOjEzM3B4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cml0YWJsZS5wbmdcIiBzdHlsZT1cImhlaWdodDo5NXB4OyB3aWR0aDo0ODhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5MZXQmcnNxdW87cyBkZVx1ZmIwMW5lIHRoZSB2YWx1ZSBvZiBhIHVuaXQgdHJpYW5nbGUgdG8gYmUgdGhlIGludGVnZXIgdmFsdWUgd3JpdHRlbiBpbiB0aGF0IHRyaWFuZ2xlLiBJbiBnZW5lcmFsLCB0aGUgdmFsdWUgb2YgYSB0cmlhbmdsZSBpcyB0aGUgc3VtIG9mIHZhbHVlcyBpbiBhbGwgaXRzIHVuaXQgdHJpYW5nbGVzLiBUaGUgXHVmYjAxZ3VyZSBvbiB0aGUgcmlnaHQgaXMgdGhlIHNhbWUgYXMgdGhlIG9uZSBhYm92ZSBidXQgd2l0aCB0aGUgc3ViLXRyaWFuZ2xlIGhhdmluZyB0aGUgbGFyZ2VzdCB2YWx1ZSBiZWluZyBoaWdobGlnaHRlZC4gV3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgc3ViLXRyaWFuZ2xlIHdpdGggdGhlIGxhcmdlc3QgdmFsdWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgc3BlY2lcdWZiMDFlZCBpbiBhIHNpbmdsZSBsaW5lIG1hZGUgb2YgaW50ZWdlcnMgKHNlcGFyYXRlZCBieSBzcGFjZXMuKSBUaGUgXHVmYjAxcnN0IGludGVnZXIgaXMgdGhlIG51bWJlciBvZiByb3dzIGluIHRoZSB0ZXN0IGNhc2UsIGFuZCB0aGUgcmVtYWluaW5nIGludGVnZXJzIGFyZSB0aGUgdmFsdWVzIG9mIHRoZSB1bml0IHRyaWFuZ2xlcyBzcGVjaVx1ZmIwMWVkIGluIGEgdG9wLWRvd24sIGxlZnQtdG8tcmlnaHQgb3JkZXIuICh0aGUgXHVmYjAxcnN0IHRlc3QgY2FzZSBpbiB0aGUgZXhhbXBsZSBiZWxvdyBpcyB0aGUgc2FtZSBhcyB0aGUgb25lIGluIHRoZSBcdWZiMDFndXJlLikgVGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgdGhlIG51bWJlciAwICh3aGljaCBpcyBub3QgcGFydCBvZiB0aGUgdGVzdCBjYXNlcy4pPFwvcD5cclxuXHJcbjxwPlRoZSBtYXhpbXVtIG51bWJlciBvZiByb3dzIGlzIDQwMC4gVGhlIGFic29sdXRlIHZhbHVlIG9mIGEgdW5pdCB0cmlhbmdsZSBpcyBsZXNzIHRoYW4gMTAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSByZXN1bHQgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+ay5cdTAwMDJWPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgayBpcyB0aGUgdGVzdCBjYXNlIG51bWJlciAoc3RhcnRpbmcgYXQgMSwpIFx1MDAwMiBpcyBhIHNpbmdsZSBzcGFjZSwgYW5kIFYgaXMgdGhlIG1heGltdW0gdmFsdWUgb2YgYSBzdWItdHJpYW5nbGUgaW4gdGhhdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d