25608번 - 장난감 섞기

문제

랑이 집사는 랑이와 메리의 조기 교육을 위해 $N$개의 수열을 주문했다.

각 수열의 길이는 $M$으로 모두 동일하고, 수열을 구성하는 수는 다를 수 있다. 주문한 수열은 모두 완제품이라서 임의로 나누거나 수정할 수 없고, 수열끼리의 순서만 마음대로 배치할 수 있다.

어떤 수열의 최대 연속합이란 그 수열에서 연속으로 몇 개의 수를 선택해서 더하는 경우들 중 가장 합이 큰 경우의 합을 의미한다. 수를 하나도 고르지 않는 경우도 가능하며, 이 때의 연속합은 0ドル$으로 정의한다.

랑이와 메리는 어떤 수열의 최대 연속합이 클수록 이 수열에 흥미를 느낀다.

랑이 집사는 가장 흥미로운 수열을 만들기 위해 $N$개의 수열의 순서를 마음대로 배치해 하나의 긴 수열을 만들고자 한다. 랑이 집사가 만든 수열의 최대 연속합을 구하는 프로그램을 작성하시오.

입력

첫 줄에 $N,ドル $M$이 공백으로 구분되어 주어진다. (1ドル \le N \le 10,ドル 1ドル \le M \le 10,000$)

둘째 줄부터 $N$줄에 걸쳐 각 수열이 한 줄에 하나씩 주어진다. 수열은 -100ドル$ 이상 100ドル$ 이하의 정수로 구성되어 있다.

출력

랑이 집사가 만든 수열의 최대 연속합을 출력한다.

제한

힌트