Background

Problem setter: LinkyChristian.

Story writer: Xiao Nuomi (xiaonuomi).

Problem Description

"That said, we did not roam around and let the fairies be born one by one.
We only carved spell marks onto the huge soul body used as material, so that they could naturally be born with a physique and personality close to humans."

A golden fairy is a "person" who is cursed with early death from the moment of birth. If not for being a monster that cannot resist it, she should never have been born in this vast mortal world, but rather as a weapon.

Whenever memories of a previous life surge up in a fairy, it is the day the countdown begins for a budding flower to wither. A fairy's memory is made up of a ray. For convenience, we may treat this ray as a number line. In her memory, there are several intervals within which memories are very easily eroded by memories of a previous life. However, since a creature's memory itself cannot be clearly observed, we can only know $m1$ start intervals $[sl_i,sr_i]$ and $m2$ end intervals $[el_j,er_j]$. In this memory, various previous-life memories will gradually emerge and erode earlier memories. When all these easily-eroded memory intervals are completely eroded, the golden fairy will "disappear". These previous-life memories can be regarded as $n$ non-overlapping subsegments on the number line. The start point and end point of each subsegment lie respectively inside one start interval and one end interval. Also, due to the nature of memory, the start and end points of different previous-life memories naturally lie in different start intervals and different end intervals.

Memory is like a rushing stream: the water babbles and flows downstream, stirring stones and silt, rising and sinking on and under the surface. Upstream, there may be steep rocks and boulders, heavy in their own right, so the water is clear and calm; the closer it gets to the sea, stones are gradually replaced by silt. Even a light breeze making small waves can stir up a muddy mess, tangling the memories into confusion. Each erosion of memory is like a surging wave: perhaps it stirs the silt, or perhaps it only nudges a boulder slightly. In numeric terms, matching the $i$-th start interval brings a contribution of $a_i$, and matching the $i$-th end interval brings a contribution of $b_i$. When these contributions reach the maximum value, the so-called "completely eroded" will happen. Now the fairies want to know what this maximum value is.

In particular, if the testdata has no solution, output $-1$.

Simplified statement:

Given $m1$ start intervals $[sl_i,sr_i]$ and $m2$ end intervals $[el_j,er_j]$. Choose $n$ non-overlapping subsegments on the number line such that the start point and end point of each subsegment lie in a start interval and an end interval, respectively. The start points of different subsegments must lie in different start intervals, and the end points of different subsegments must lie in different end intervals. Matching the $i$-th start interval yields contribution $a_i$, and matching the $i$-th end interval yields contribution $b_i$. The total contribution equals the sum of lengths of the chosen subsegments plus the contributions brought by matched intervals. Find the maximum possible total contribution.

Note: The length of a subsegment $[l,r]$ is defined as $r-l$. Two subsegments "overlap" means there exists an interval of length $>0$ that is contained in both subsegments.

If there is no solution, output $-1$.

Input Format

The first line contains three integers $n,m1,m2$.

The second line contains $2\times m1$ integers representing $sl_1,sr_1,sl_2,sr_2,\dots , sl_{m1},sr_{m1}$.

The third line contains $2\times m2$ integers representing $el_1,er_1,el_2,er_2,\dots , el_{m2},er_{m2}$.

The fourth line contains $m1$ numbers representing $a_1,a_2,\dots ,a_{m1}$.

The fifth line contains $m2$ numbers representing $b_1,b_2,\dots ,b_{m2}$.

Output Format

Output one integer, the maximum total contribution.

2 2 2
1 3 7 8
4 5 9 10
0 0
0 0

7

2 3 3
1 2 3 5 100 200
5 7 9 10 400 500
1000 1000 0
1000 1000 0

4009

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

14

2 2 2
1 2 4 5
6 7 8 9
12 33
23 1

-1

Hint

For the first sample, match the start interval $[1,3]$ with the end interval $[4,5]$, choose subsegment $[1,5]$ with length $5-1=4$. Then match the start interval $[7,8]$ with the end interval $[9,10]$, choose subsegment $[7,10]$ with length $10-7=3$. The total chosen length is $4+3=7$. This satisfies that there are $n$ matches between start and end intervals and the chosen subsegments do not overlap, and the total contribution is maximized.
For the second sample, match $[1,2]$ with $[9,10]$, and match $[3,5]$ with $[5,7]$, choosing subsegments $[1,10]$ and $[5,5]$.
For the third sample, match $[1,2]$ with $[3,10]$, and match $[4,5]$ with $[7,7]$, choosing subsegments $[1,5]$ and $[5,7]$.
subtask1: For $15\%$ of the testdata, $n<=5,m1,m2<=10$.
subtask2: For $100\%$ of the testdata, $n,m1,m2<=100$, and all values in the problem are $\le 10^3$.

Translated by ChatGPT 5