Problem Description

THU and PKU both offer a set of courses. THU has $n$ courses, and PKU has $m$ courses.

For THU, the $i$-th course has a category $a_i$ and a fun factor $x_i$. For PKU, the $i$-th course has a category $b_i$ and a fun factor $y_i$. It is guaranteed that the elements in $a$ are unique, and the elements in $b$ are unique. However, $a$ and $b$ may share some common elements.

You can choose to attend the courses from THU numbered $l_1$ to $r_1$, and the fun factor you gain is the sum of the fun factors of all the courses you attend. Similarly, you can attend the courses from PKU numbered $l_2$ to $r_2$, and the fun factor you gain is also the sum of the fun factors of all the courses you attend. (Of course, you can choose to attend courses from only one university or none at all.)

You cannot attend courses of the same category twice. This means if there are elements in $a_{l_1 \sim r_1}$ that are the same as elements in $b_{l_2 \sim r_2}$, then this course selection scheme does not satisfy your preferences.

You need to find the maximum possible fun factor from the course selection schemes and the specific arrangement.

Input Format

The first line contains two integers $n$ and $m$.

The next four lines each contain an integer sequence, representing $a$, $x$, $b$, and $y$ respectively. The lengths of these sequences are $n$, $n$, $m$, and $m$ respectively.

Output Format

The first line contains an integer representing the maximum fun factor.

The second line contains two integers $l_1$ and $r_1$. If you do not plan to attend courses at THU, output 0 0.

The third line contains two integers $l_2$ and $r_2$. If you do not plan to attend courses at PKU, output 0 0.

Sample Input and Output

Sample Input #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

Sample Output #1

39
2 6
2 4

Sample Input #2

2 3
1 2
1 4
2 3 1
17 2 15

Sample Output #2

34
0 0
1 3

Sample Input #3

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

Sample Output #3

19
1 1
3 3

Notes

Sample Explanation

For Sample Group #1:

The optimal solution is as shown in the sample, with the sum of course qualities being $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$.

For Sample Group #2:

Since the quality of PKU's courses numbered 1 and 2 is much higher than that of THU's corresponding courses, the optimal solution is to not attend THU's courses and instead attend PKU's courses numbered 1 through 3.

Data Range

Note: This problem only includes partial data. For complete data, please refer to LOJ P2773 for evaluation.

For all data, the following conditions are satisfied: $1 \le a_i, b_i \le n+m$, $1 \le x_i, y_i \le 10^9$, $a_i \ne a_j (i \ne j)$, $b_i \ne b_j (i \ne j)$.

见题面 Input 部分

见题面 Output 部分