시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 218 153 134 75.706%

문제

어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.

예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.

양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법을 여러 가지가 있다. 이때, 합의 최솟값을 구하시오.

참고로 수열을 통채로 그룹 1개에 넣을 수 있다. 그럼 이때, 수의 합은 수열의 합이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 첫째 줄에 수열의 크기 M이 주어진다. (1 <= M <= 10,000) 그 다음 줄부터는 그 수열에 들어있는 수가 주어지고, 한 줄에 10개씩 나누어서 주어진다. 따라서 마지막 줄은 수가 10개가 아닐 수도 있다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 문제에서 설명한 가장 작은 합을 출력한다.

예제 입력 1

3
6
2 5 1 3 3 7
6
1 2 3 4 5 6
20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

예제 출력 1

7
21
2
W3sicHJvYmxlbV9pZCI6IjI2OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjlcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWQ2Y1x1YWMwNCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHViYTc0XHVjMTFjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0XHVjMTFjLCBcdWFjMDEgXHVhZGY4XHViOGY5XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWMxOVx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMiwgNSwgMSwgMywgMywgN1x1Yzc0MCAoMiwgNSksICgxLCAzLCAzKSwgKDcpXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWIyMDRcdWJhNzQgXHVhYzAxIFx1YWRmOFx1YjhmOVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NCA3XHViODVjIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHVkNTY5XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzM4XHVhY2UwXHViODVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQxYjVcdWNjNDRcdWI4NWMgXHVhZGY4XHViOGY5IDFcdWFjMWNcdWM1ZDAgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmYyBcdWM3NzRcdWI1NGMsIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbHQ7PSBUICZsdDs9IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gTSAmbHQ7PSAxMCwwMDApIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgMTBcdWFjMWNcdWM1MjkgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHVjMjE4XHVhYzAwIDEwXHVhYzFjXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXF1YWwgU3VtIFBhcnRpdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gb2YgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIGlzIGEgZ3JvdXBpbmcgb2YgdGhlIG51bWJlcnMgKGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBvcmlnaW5hbCBzZXF1ZW5jZSkgaW4gc3VjaCBhIHdheSB0aGF0IGVhY2ggZ3JvdXAgaGFzIHRoZSBzYW1lIHN1bS4gRm9yIGV4YW1wbGUsIHRoZSBzZXF1ZW5jZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT4yIDUgMSAzIDMgNyZuYnNwOzxcL3ByZT5cclxuXHJcbjxwPm1heSBiZSBncm91cGVkIGFzOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPigyIDUpICgxIDMgMykgKDcpJm5ic3A7PFwvcHJlPlxyXG5cclxuPHA+dG8geWllbGQgYW4gZXF1YWwgc3VtIG9mIDcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBwYXJ0aXRpb24gdGhhdCBwdXRzIGFsbCB0aGUgbnVtYmVycyBpbiBhIHNpbmdsZSBncm91cCBpcyBhbiBlcXVhbCBzdW0gcGFydGl0aW9uIHdpdGggdGhlIHN1bSBlcXVhbCB0byB0aGUgc3VtIG9mIGFsbCB0aGUgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHRha2VzIGFzIGlucHV0IGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMgYW5kIHJldHVybnMgdGhlIHNtYWxsZXN0IHN1bSBmb3IgYW4gZXF1YWwgc3VtIHBhcnRpdGlvbiBvZiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBkYXRhIHNldCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBmb2xsb3dlZCBieSBhIHNwYWNlLCBmb2xsb3dlZCBieSBhIGRlY2ltYWwgaW50ZWdlciBNLCAoMSAmbGU7IE0gJmxlOyAxMDAwMCksIGdpdmluZyB0aGUgdG90YWwgbnVtYmVyIG9mIGludGVnZXJzIGluIHRoZSBzZXF1ZW5jZS4gVGhlIHJlbWFpbmluZyBsaW5lKHMpIGluIHRoZSBkYXRhc2V0IGNvbnNpc3Qgb2YgdGhlIHZhbHVlcywgMTAgcGVyIGxpbmUsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGxhc3QgbGluZSBpbiB0aGUgZGF0YXNldCBtYXkgY29udGFpbiBsZXNzIHRoYW4gMTAgdmFsdWVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciwgYSBzcGFjZSwgYW5kIHRoZSBzbWFsbGVzdCBzdW0gZm9yIGFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gb2YgdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==