A, B 두 마을의 주민들이 모여서 줄다리기 시합을 하려고 한다.

줄다리기에 참여할 사람들은 운동장에 각 동네별로 각각 한 줄씩 늘어서 있다.

우리는 이 줄을 각각 A줄, B줄이라고 부르기로 한다.

우리는 A줄(B줄)을 A1, A2, A3 (B1, B2, B3) 3개로 잘라

각 A1:B1, A2:B2, 그리고 A3:B3로 짝을 지어 모두 3번의 줄다리기 시합을 하려고 한다.

우리는 A1, A2, A3, B1, B2, B3 각각을 단위 줄이라고 부른다. 그리고 단위 줄에 속한 사람 들의 몸무게의 합을 단위 줄의 무게라고부르기로 한다.

이 문제에서 A, B줄은 각 줄에 늘어선 사람들의 몸무게를 나타내는 정수로 표시된다.

예를 들어 10명과 8명의 사람으로구성된 A, B 줄이 다음과 같다고 하자.

A: 62,34,54,26,65,40,30,29,35,32 B: 44,45,66,76,35,60,34,60

우리는 아래와 같이 2개의 ‘|’를 사용하여 분리된 각 단위 줄을 나타내고자 한다.

A: 62,34,54 | 26,65,40,30 | 29,35,32 B: 44,45,66 | 76,35,60 | 34,60

위의 예에서 단위 줄 A1은 <62,34,54>이며, 그 무게는 150이다. 그리고 단위줄 B3은 <34, 60>이며 그 무게는 94가된다.

그런데 시합을 좀 더 흥미롭게 만들기 위하여 우리는 반드시 다음의 규칙을 만족시키고자 한다.

[규칙1] A, B줄에 늘어선 사람들의 처음 정해진 순서는 중간에 바꿀 수 없다.

[규칙2] 각 단위 줄은 한 명 이상으로구성된다.

[규칙3] 시합을 위하여 대응하는 각 단위 줄의 무게의 차이는 모두 50 이하가되어야 한다.

예를 들어 A1을 <62,34>로, B1을 <44,45,66>로 편성하면 이것은 규칙3을 위반하는 것이므로 그러한 단위 줄 편성은 불가능하다.

대응하는3개 단위 줄 무게의 차이 중, 가장 큰 값을 줄다리기 값이라고 한다면,

우리는 시합을 흥미롭게 진행하기 위하여 가장 작은 줄다리기 값을 가지는 단위 줄 편성을 찾고자 한다.

만일 대응하는 단위 줄의 무게 차이가 각각 10, 15, 12 라고 한다면 이 상황에서의 줄다리기 값은 15가 된다.

만일 다르게 단위 줄을 편성하여 그 무게 차이가 각각 8, 17, 4 이라고 하면 그 줄다리기 값은 17이 되어 전자가 후자보다 더 나은 편성이 된다.

A, B줄의 몸무게 값을 순서대로 받아서 줄다리기 값을 최소로 하는 단위 줄 편성을 찾아내는 프로그램을 작성하시오.

줄다리기 timer 1s memory 256MB

줄다리기 1s 256MB