시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 6 5 17.241%

문제

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

이 때, 그림에서 서로 다른 부분 삼각형은 총 13개가 있다. (N=2인 삼각형이 2개, 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+XHVjNzc0IFx1YjU0YywgXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViZDgwXHViZDg0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWNkMWQgMTNcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiAoTj0yXHVjNzc4IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCAyXHVhYzFjLCBOPTNcdWM3NzggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IDFcdWFjMWMpPFwvcD5cclxuXHJcbjxwPk4gPSAxXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWJkODBcdWJkODQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIDFcdWFjMWMsIDJcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDVcdWFjMWMsIDNcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IDEzXHVhYzFjLCA0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCAyN1x1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMsIFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjMzY4XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyXHVjNzQwIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzEyXHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cjEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjEyNnB4OyB3aWR0aDoxMzNweFwiIFwvPlx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViZDgwXHViZDg0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YzkwNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjMjJiXHVjNzkwXHViMjk0IFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YWMxMlx1Yzc3NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4LCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzkwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgNDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YjJlOFx1YzcwNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YWMxMlx1Yzc1OCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NDAgMTAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJkODBcdWJkODQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDkwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFkZGluZyB1cCBUcmlhbmdsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHIucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjEzMHB4OyB3aWR0aDoxMzRweFwiIFwvPlRha2UgYSBsb29rIGF0IHRoZSB0cmlhbmdsZSBvbiB0aGUgcmlnaHQuIEl0IGlzIG1hZGUgb2YgOSAodW5pdCkgdHJpYW5nbGVzIGFycmFuZ2VkIGluIHRocmVlIHJvd3MgKE49MykuIE5lZWRsZXNzIHRvIHNheSwgYSB1bml0IHRyaWFuZ2xlIGlzIGEgdHJpYW5nbGUgd2l0aCBOPTEuIElmIHlvdSBzdHVkeSB0aGUgXHVmYjAxZ3VyZSBmb3IgZmV3IHNlY29uZHMsIHlvdSZyc3F1bztsbCByZWFsaXplIHRoYXQgeW91IGNhbiBcdWZiMDFuZCAxMyBkaVx1ZmIwMGVyZW50IHRyaWFuZ2xlcyAod2hpY2ggd2UmcnNxdW87bGwgY2FsbCBzdWItdHJpYW5nbGVzLikgT2YgdGhlc2UgMTMgc3ViLXRyaWFuZ2xlcyB3ZSBoYXZlOiBOaW5lIHVuaXQgdHJpYW5nbGU7IHRocmVlIHdpdGggTj0yLCBhbmQgb25lIHdpdGggTj0zLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIHRhYmxlIGxpc3RzIHRoZSBudW1iZXIgb2Ygc3ViLXRyaWFuZ2xlcyBpbiBhcnJhbmdlbWVudHMgd2l0aCBOICZsdDsgNS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cjEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjEyNnB4OyB3aWR0aDoxMzNweFwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJpdGFibGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTVweDsgd2lkdGg6NDg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TGV0JnJzcXVvO3MgZGVcdWZiMDFuZSB0aGUgdmFsdWUgb2YgYSB1bml0IHRyaWFuZ2xlIHRvIGJlIHRoZSBpbnRlZ2VyIHZhbHVlIHdyaXR0ZW4gaW4gdGhhdCB0cmlhbmdsZS4gSW4gZ2VuZXJhbCwgdGhlIHZhbHVlIG9mIGEgdHJpYW5nbGUgaXMgdGhlIHN1bSBvZiB2YWx1ZXMgaW4gYWxsIGl0cyB1bml0IHRyaWFuZ2xlcy4gVGhlIFx1ZmIwMWd1cmUgb24gdGhlIHJpZ2h0IGlzIHRoZSBzYW1lIGFzIHRoZSBvbmUgYWJvdmUgYnV0IHdpdGggdGhlIHN1Yi10cmlhbmdsZSBoYXZpbmcgdGhlIGxhcmdlc3QgdmFsdWUgYmVpbmcgaGlnaGxpZ2h0ZWQuIFdyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlIHN1Yi10cmlhbmdsZSB3aXRoIHRoZSBsYXJnZXN0IHZhbHVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgaW4gYSBzaW5nbGUgbGluZSBtYWRlIG9mIGludGVnZXJzIChzZXBhcmF0ZWQgYnkgc3BhY2VzLikgVGhlIFx1ZmIwMXJzdCBpbnRlZ2VyIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgdGVzdCBjYXNlLCBhbmQgdGhlIHJlbWFpbmluZyBpbnRlZ2VycyBhcmUgdGhlIHZhbHVlcyBvZiB0aGUgdW5pdCB0cmlhbmdsZXMgc3BlY2lcdWZiMDFlZCBpbiBhIHRvcC1kb3duLCBsZWZ0LXRvLXJpZ2h0IG9yZGVyLiAodGhlIFx1ZmIwMXJzdCB0ZXN0IGNhc2UgaW4gdGhlIGV4YW1wbGUgYmVsb3cgaXMgdGhlIHNhbWUgYXMgdGhlIG9uZSBpbiB0aGUgXHVmYjAxZ3VyZS4pIFRoZSBsYXN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHRoZSBudW1iZXIgMCAod2hpY2ggaXMgbm90IHBhcnQgb2YgdGhlIHRlc3QgY2FzZXMuKTxcL3A+XHJcblxyXG48cD5UaGUgbWF4aW11bSBudW1iZXIgb2Ygcm93cyBpcyA0MDAuIFRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiBhIHVuaXQgdHJpYW5nbGUgaXMgbGVzcyB0aGFuIDEwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgcmVzdWx0IHVzaW5nIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48cHJlPmsuXHUwMDAyVjxcL3ByZT5cclxuXHJcbjxwPndoZXJlIGsgaXMgdGhlIHRlc3QgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGF0IDEsKSBcdTAwMDIgaXMgYSBzaW5nbGUgc3BhY2UsIGFuZCBWIGlzIHRoZSBtYXhpbXVtIHZhbHVlIG9mIGEgc3ViLXRyaWFuZ2xlIGluIHRoYXQgdGVzdCBjYXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==