P10656 [ROI 2017] Learning Trajectory (Day 2)

THU and PKU offer a batch of courses at the same time. THU has $n$ courses, and PKU has $m$ courses. For THU, the category of course $i$ is $a_i$, and its fun value is $x_i$. For PKU, the category of course $i$ is $b_i$, and its fun value is $y_i$. It is guaranteed that all elements in $a$ are distinct, and all elements in $b$ are distinct, but there may be common elements between $a$ and $b$. You may choose to take courses $l_1 \sim r_1$ at THU, and the fun you gain is the sum of fun values of all courses you take. At the same time, you may choose to take courses $l_2 \sim r_2$ at PKU, and the fun you gain is also the sum of fun values of all courses you take. (Of course, you may also choose to take courses from only one university, or even take none.) You cannot take the same category of course twice. That is, if there exists an element in $a_{l_1 \sim r_1}$ that is the same as an element in $b_{l_2 \sim r_2}$, then this course-taking plan is not allowed. You need to find, among all possible plans, the maximum total fun value and a specific arrangement.

The first line contains two integers $n, m$. The next four lines each contain an integer sequence, representing $a, x, b, y$ in the statement. The lengths of these sequences are $n, n, m, m$, respectively.

The first line contains one integer, the maximum fun value. The second line contains two integers $l_1, r_1$. If you do not plan to take courses at THU, output `0 0`. The third line contains two integers $l_2, r_2$. If you do not plan to take courses at PKU, output `0 0`.

#### Sample Explanation For sample set #1: The optimal solution is as shown in the sample. The sum of course quality is $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$. For sample set #2: Since PKU's courses $1$ and $2$ have much higher quality than the corresponding courses at THU, the optimal solution is to not take any courses at THU, and instead take courses $1 \sim 3$ at PKU. #### Constraints Note: This problem only provides part of the testdata. For the full testdata, please go to [LOJ P2773](https://loj.ac/p/2773). For all data, it holds that: $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)$. | Subtask ID | Score | $1 \le n, m \le$ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $50$ | | $2$ | $10$ | $100$ | | $3$ | $10$ | $300$ | | $4$ | $10$ | $500$ | | $5$ | $10$ | $2000$ | | $6$ | $5$ | $5000$ | | $7$ | $5$ | $10^4$ | | $8$ | $10$ | $3 \times 10^4$ | | $9$ | $10$ | $10^5$ | | $10$ | $10$ | $2.5 \times 10^5$ | | $11$ | $10$ | $5 \times 10^5$ | Translated by ChatGPT 5