우애 좋은 형제

N x N개의 단위 구역으로 이루어진 논이 있다. 각 구역에는 예상 쌀 수확량(가마)이 주어진다.

두 형제는 각 열마다 아래쪽에서부터 몇 개의 구역을 형에게 주고, 나머지 위쪽 구역을 동생에게 주기로 했다. i번째 열에서 형이 받는 구역 수를 h_i라고 하자. 배정은 계단 모양이어야 하므로 0 <= h_1 <= h_2 <= ... <= h_N <= N을 만족해야 한다.

형이 받는 구역들의 예상 수확량 합과 동생이 받는 구역들의 예상 수확량 합의 차이가 최소가 되도록 논을 나누어야 한다. 최소 차이와 그때의 h_1, h_2, ..., h_N 중 하나를 구하라.

첫째 줄에 논의 크기 N (2 <= N <= 20)이 주어진다.

다음 N개의 줄에는 논의 위쪽 행부터 아래쪽 행까지 각 행의 예상 수확량이 주어진다. 각 줄에는 0 이상 100 이하의 정수 N개가 공백으로 구분되어 주어진다.

첫째 줄에 두 형제의 예상 수확량 차이의 최솟값을 출력한다.

둘째 줄에 첫 번째 열부터 N번째 열까지 형이 받는 구역 수 h_1, h_2, ..., h_N을 공백으로 구분해 출력한다. 최적의 배정이 여러 가지이면 그중 하나를 출력한다.