시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 48 15 13 52.000%

문제

A×1 크기의 상자와 B×1 크기의 상자가 있다. 이 안에 각각 A개, B개의 구슬이 들어 있는데, 각 구슬에는 1부터 N까지의 정수가 적혀 있다.

상자의 제일 아랫부분에는 구멍이 뚫려 있어서, 이 구멍을 통해서 제일 아래 있는 구슬에 적혀 있는 번호를 볼 수도 있고, 구슬을 뺄 수도 있다. 이와 같은 상자 안의 구슬을 이용하여 다음 세 가지 작업 중 하나를 할 수 있다.

  1. A×1 크기의 상자의 제일 아랫부분의 구슬을 뺀다. (점수 없음)
  2. B×1 크기의 상자의 제일 아랫부분의 구슬을 뺀다. (점수 없음)
  3. A×1 크기의 상자의 제일 아랫부분의 구슬과 B×1 크기의 상자의 제일 아랫부분의 구슬을 동시에 뺀다. 그리고 두 개의 구슬에 적혀 있는 수를 이용하여 점수를 계산한 뒤, 총점(0부터 시작)에 이를 더한다.

이와 같은 과정을 두 개의 상자에 구슬이 남아있지 않을 때까지 반복하려 한다. 이 때 얻을 수 있는 가장 높은 점수와 그 때 수행한 작업들을 구하는 프로그램을 작성하시오.

예를 들어 다음과 같은 A=B=N=2인 경우를 보자.

-1 2
1 -2
2 2
1 1

위쪽 표는 점수표이고 아래쪽은 상자의 모양이다. 왼쪽 상자에서 1, 오른쪽 상자에서 1을 꺼냈을 때의 점수가 -1점이고, 왼쪽 상자에서 1, 오른쪽 상자에서 2를 꺼냈을 때의 점수가 2점인 식이다. 이때는 2 3 1의 순서로 작업을 수행하면 2점을 얻을 수 있고, 이 경우의 점수가 제일 높다.

입력

첫째 줄에 세 정수 N, A, B(1 ≤ N, A, B ≤ 1,000)가 주어진다. 다음 N개의 줄에는 N개의 정수로 점수표가 주어진다. 다음 줄에는 A개의 정수로 상자 안에 들어 있는 구슬에 적혀있는 번호가 아래쪽 구슬부터 주어진다. 다음 줄에는 B개의 정수로 상자 안에 들어 있는 구슬에 적혀있는 번호가 역시 아래쪽부터 주어진다. 점수표의 점수는 -1,000이상 1,000 이하이다.

출력

첫째 줄에 얻을 수 있는 최대 점수를 출력한다. 다음 줄에는 수행한 순서대로 작업 번호를 출력한다.

예제 입력

2 2 2
-1 2
1 -2
1 2
1 2

예제 출력

2
2 3 1

힌트