learningtrack

Learning Track

The winner of a student competition received internship offers from two universities.

While preparing his plans of study, he learned the teaching quality rating of each discipline at these universities.

The curriculum of the first university consists of a sequence of \(n\) different disciplines listed in chronological order \(a_1, a_2, \ldots, a_n\), with ratings \(x_1, x_2, \ldots, x_n\) respectively. The second university's curriculum also consists of a sequence of \(m\) different disciplines listed in chronological order \(b_1, b_2, \ldots, a_m\), with ratings \(y_1, y_2, \ldots, y_m\) respectively.

The student has the option of making a plan of study at the first university to take some sequence of disciplines at curriculum positions \(l_a\) through \(r_a\) inclusive \((1 \leq l_a \leq r_a \leq n)\), or decline an internship at the first university. Similarly, he or she may plan to study some disciplines \(l_b\) through \(r_b\) inclusive \((1 \leq l_b \leq r_b \leq m)\) in the second university, or decline the internship at the second university.

It does not make sense to study the same discipline twice at different universities, so all the disciplines in the two chosen plans of study must be different.

Write a program to determine the highest possible sum of ratings of the studied disciplines, given the student makes an optimal study plan.

Limits

\(1 \leq n, m \leq 5 * 10^5\), \(1 \leq a_i, b_i \leq n + m\), \(a_i \neq a_j\), \(b_i \neq b_j\), \(1 \leq x_i, y_i \leq 10^9\)

Subtask #	Score	Constraints
1	10	\(n, m \leq 50\)
2	10	\(n, m \leq 100\)
3	10	\(n, m \leq 300\)
4	10	\(n, m \leq 500\)
5	10	\(n, m \leq 2000\)
6	5	\(n, m \leq 5000\)
7	5	\(n, m \leq 10000\)
8	10	\(n, m \leq 30000\)
9	10	\(n, m \leq 100000\)
10	10	\(n, m \leq 250000\)
9	10	No additional constraints

Input format

The first line of input contains integers \(n\) and \(m\) - the number of disciplines in the first and second university degree programs respectively \((1 \leq n, m \leq 500,000)\).

The second line of input contains \(n\) integers \(a_i\) - the disciplines included in the first university's curriculum, listed in chronological order \((1 \leq a_i \leq n + m)\).

The third line of input contains \(n\) integers \(x_i\) - the ratings of the disciplines included in the first university's curriculum, listed in the same order as the disciplines \(a_i\) \((1 \leq x_i \leq 10^9)\).

The fourth line of input contains \(m\) integers \(b_i\) - the disciplines included in the second university's curriculum, listed in chronological order \((1 \leq b_i \leq n + m)\).

The fifth line of input contains \(m\) integers \(y_i\) - the ratings of the disciplines included in the of the second university's curriculum, listed in the same order as the disciplines \(b_i\) \((1 \leq y_i \leq 10^9)\).

Output format

The first line of output should contain an integer \(s\) - the largest possible sum of discipline ratings.

The second line of output should contain two integers \(l_a\), \(r_a\) - the range of courses chosen from the curriculum of the first university, or "0 0" if the student declined an internship at the first university.

The third line of output should contain two integers \(l_b\), \(r_b\) - the range of courses chosen from the curriculum of the second university, or "0 0" if the student declined an internship at the second university.

If there are several possible answers, you may output any one of them.

Samples

Sample Input 1	Sample Output 1
7 5 3 1 4 8 6 9 2 2 7 4 10 1 5 3 9 2 11 3 8 3 5 3 4 12	39 2 6 2 4

The optimal solution is to take the courses described in the output, yielding a sum of ratings of \((7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39\). One suboptimal combination which could have been taken is \((7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38\).

Sample Input 2	Sample Output 2
2 3 1 2 1 4 2 3 1 17 2 15	34 0 0 1 3

In this testcase, the first and third disciplines at the second university are rated so highly compared to the corresponding disciplines at the first university, that the optimal choicen is to take the entire internship at the second university and forgo an internship at the first university.

Sample Input 3	Sample Output 3
3 3 4 2 1 10 1 2 5 4 2 1 2 9	19 1 1 3 3