Maximizing Enjoyment in University Courses

THU and PKU are offering courses concurrently. THU has \(n\) courses and PKU has \(m\) courses. In THU, the \(i\)th course has category \(a_i\) and enjoyment \(x_i\); in PKU, the \(i\)th course has category \(b_i\) and enjoyment \(y_i\). It is guaranteed that within the THU list the categories (i.e. the array \(a\)) are pairwise distinct, and within the PKU list the categories (i.e. the array \(b\)) are pairwise distinct, though the two lists may share some common elements.

You are allowed to choose a contiguous block of courses from THU, i.e. courses from index \(l_1\) to \(r_1\), and a contiguous block from PKU, i.e. courses from index \(l_2\) to \(r_2\). You may also choose courses from only one university or even choose none. The total enjoyment is the sum of the enjoyments of the chosen courses.

However, if the two chosen blocks have any course category in common (that is, if \(\{a_{l_1},a_{l_1+1},\ldots,a_{r_1}\}\) and \(\{b_{l_2},b_{l_2+1},\ldots,b_{r_2}\}\) share at least one element), then the plan is invalid.

Your task is to find the maximum total enjoyment possible and print a valid plan that achieves it. In the output, if you choose no courses from a university, output 0 -1 for that university (i.e. \(l=0, r=-1\)).

inputFormat

The input consists of five lines:

• The first line contains two integers \(n\) and \(m\).
• The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\), representing the course categories for THU.
• The third line contains \(n\) integers \(x_1,x_2,\ldots,x_n\), representing the enjoyment values for THU courses.
• The fourth line contains \(m\) integers \(b_1,b_2,\ldots,b_m\), representing the course categories for PKU.
• The fifth line contains \(m\) integers \(y_1,y_2,\ldots,y_m\), representing the enjoyment values for PKU courses.

outputFormat

Output two lines. The first line should contain a single integer, the maximum total enjoyment. The second line should contain four integers \(l_1\), \(r_1\), \(l_2\), \(r_2\) representing the selected indices for THU and PKU respectively (use 0 -1 for a university if no course is selected from that university).

sample

3 3
1 2 3
1 2 3
2 4 5
10 1 1

13
1 1 1 3