학습 경로

한 학생이 두 대학으로부터 인턴십 제안을 받았습니다. 학습 계획을 세우면서 그는 두 대학의 각 과목에 대한 강의 품질 평점을 알게 되었습니다.

첫 번째 대학의 교육 과정은 시간 순으로 나열된 서로 다른 $n$개의 과목 $a_1, a_2, \ldots, a_n$으로 이루어지며, 각 과목의 평점은 차례대로 $x_1, x_2, \ldots, x_n$입니다. 두 번째 대학의 교육 과정은 시간 순으로 나열된 서로 다른 $m$개의 과목 $b_1, b_2, \ldots, b_m$으로 이루어지며, 각 과목의 평점은 차례대로 $y_1, y_2, \ldots, y_m$입니다.

학생은 첫 번째 대학에서 교육 과정의 $l_a$번째부터 $r_a$번째까지 (양 끝 포함, $1 \le l_a \le r_a \le n$) 과목을 듣는 계획을 세우거나, 첫 번째 대학의 인턴십을 포기할 수 있습니다. 마찬가지로 두 번째 대학에서는 $l_b$번째부터 $r_b$번째까지 (양 끝 포함, $1 \le l_b \le r_b \le m$) 과목을 듣는 계획을 세우거나, 두 번째 대학의 인턴십을 포기할 수 있습니다.

같은 과목을 두 대학에서 중복으로 들을 이유가 없으므로, 선택한 두 학습 계획에 포함된 과목은 모두 달라야 합니다.

학생이 수강하는 과목 평점의 합이 최대가 되도록 학습 계획을 정하는 프로그램을 작성하십시오.

첫 줄에는 첫 번째 대학과 두 번째 대학의 교육 과정에 있는 과목 수 정수 $n$과 $m$이 주어집니다 ($1 \le n, m \le 500\,000$).

둘째 줄에는 시간 순으로 나열된 첫 번째 대학의 과목 $n$개 $a_i$가 주어집니다 ($1 \le a_i \le n + m$).

셋째 줄에는 같은 순서로 나열된 과목 $n$개의 평점 $x_i$가 주어집니다 ($1 \le x_i \le 10^9$).

넷째 줄에는 시간 순으로 나열된 두 번째 대학의 과목 $m$개 $b_i$가 주어집니다 ($1 \le b_i \le n + m$).

다섯째 줄에는 같은 순서로 나열된 과목 $m$개의 평점 $y_i$가 주어집니다 ($1 \le y_i \le 10^9$).

첫 줄에는 얻을 수 있는 평점 합의 최댓값 $r$을 출력합니다.

둘째 줄에는 첫 번째 대학 학습 계획의 첫 과목과 마지막 과목의 위치 $l_a$, $r_a$를 출력합니다. 첫 번째 대학의 인턴십을 포기한다면 0 0을 출력합니다.

셋째 줄에는 두 번째 대학에 대해 같은 형식으로 $l_b$, $r_b$를 출력합니다. 두 번째 대학의 인턴십을 포기한다면 0 0을 출력합니다.

정답이 여러 개라면 그중 아무거나 출력해도 됩니다.

첫 번째 테스트에서 제시된 학습 계획은 $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$의 합계로 이어집니다. 첫 번째 대학에서 둘째와 셋째 과목만 듣고 두 번째 대학의 과정 전체를 듣는다면 합계는 $(7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38$입니다.

두 번째 테스트에서는 두 번째 대학의 첫 번째 과목과 세 번째 과목의 평점이 첫 번째 대학의 대응 과목보다 훨씬 높습니다. 그래서 가장 유리한 선택은 두 번째 대학의 과정 전체를 듣고 첫 번째 대학의 인턴십을 포기하는 것입니다.