시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 72 21 15 29.412%

문제

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줄의 몸무게 값을 순서대로 받아서 줄다리기 값을 최소로 하는 단위 줄 편성을 찾아내는 프로그램을 작성하시오.

입력

첫째 줄에는 A, B줄의 사람 수를 나타내는 N과 M이 각각 주어진다. 두 번째, 세 번째 줄에는 A, B줄을 나타내는 N개, M개의 정수들이 빈칸을 사이에 두고 주어진다. 단, N과 M은 3 이상 30,000 이하의 정수이며, 각 사람들의 몸무게는 20 이상, 100 이하의 정수이다.

출력

첫째 줄에는 A에 대하여 최소의 줄다리기 값을 가지는 단위 줄 A1, A2, A3에 속한 사람 수를 차례대로 출력한다. 그 다음 줄에는 같은 방식으로 B에 대하여 3개의 정수를 출력한다. 예를 들어 만일 7명, 5명으로 구성된 두 줄에서 최소의 줄다리기 값을 가지는 편성이 A: 20, 20, 20 | 60 | 40, 30, 20, 그리고 B: 61 | 32, 30 | 71, 22 이라면 답으로는 다음을 출력해야 한다.

3 1 3
1 2 2

만일 각각 3명으로 구성된 A, B 두 줄의 구성이 A: 20, 20, 20 이고 B: 90, 30, 30 일 경우라면 앞서 말한 규칙을 모두 만족하는 단위 줄 편성이 불가능하다. 이렇게 편성이 불가능한 경우에는 -1을 첫 줄에 출력하면 된다. 입력에 따라서 어떤 경우에는 최소의 줄다리기 값을 가지는 단위 줄 편성이 한 개 이상 존재할 수도 있는데, 그러한 경우에는 그 중 한 가지만 출력하면 된다.

예제 입력

10 8
62 34 54 26 65 40 30 29 35 32
44 45 66 76 35 60 34 60

예제 출력

3 4 3
3 3 2

힌트