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,\dots ,a_n$, with ratings $x_1,x_2,\dots ,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,\dots ,a_m$, with ratings $y_1,y_2,\dots ,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\le l_a\le r_a\le 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\le l_b\le r_b\le 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\le n,m\le 5\ast {10}^5$, $1\le a_i,b_i\le n+m$, $a_i\ne a_j$, $b_i\ne b_j$, $1\le x_i,y_i\le {10}^9$

Subtask #	Score	Constraints
1	10	$n,m\le 50$
2	10	$n,m\le 100$
3	10	$n,m\le 300$
4	10	$n,m\le 500$
5	10	$n,m\le 2000$
6	5	$n,m\le 5000$
7	5	$n,m\le 10000$
8	10	$n,m\le 30000$
9	10	$n,m\le 100000$
10	10	$n,m\le 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\le n,m\le 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\le a_i\le 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\le x_i\le {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\le b_i\le 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\le y_i\le {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