장난감 섞기

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

각 수열의 길이는 $M$으로 모두 같지만, 수열을 구성하는 수는 수열마다 다를 수 있다. 주문한 수열은 모두 완제품이라 임의로 나누거나 수정할 수 없고, 수열의 순서만 자유롭게 정할 수 있다.

수열의 최대 연속합은 그 수열에서 연속된 수를 골라 더했을 때 얻을 수 있는 합 중 가장 큰 값이다. 아무 수도 고르지 않는 경우도 허용하며, 이때의 연속합은 $0$으로 정의한다.

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

랑이 집사는 가장 흥미로운 수열을 만들려고 $N$개의 수열을 원하는 순서로 이어 붙여 하나의 긴 수열을 만들려고 한다. 가능한 모든 순서 중에서 최대 연속합이 가장 큰 값을 구하는 프로그램을 작성하시오.

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

둘째 줄부터 $N$줄에 걸쳐 각 수열이 한 줄에 하나씩 주어진다. 수열의 수는 $-100$ 이상 $100$ 이하의 정수이다.

랑이 집사가 수열을 배치해서 만들 수 있는 최대 연속합 중 가장 큰 값을 출력한다.