Problem Description

Golden fairies, born under an early death curse, are weapons that should not exist in this vast world unless they are indomitable by monsters. Whenever memories of a past life flood a fairy's mind, it marks the beginning of the countdown for a bud to wither. The fairies' memories are composed of a ray, which we can simplify as a number line. Within their memories, there are several intervals where the recollections are easily eroded by past life memories. However, due to the nature of biological memories, we can only ascertain their $m1$ starting intervals $[sl_i, sr_i]$ and $m2$ ending intervals $[el_j, er_j]$. As these vulnerable memory intervals are eroded, the golden fairy will "disappear." These past life memories can be considered as $n$ non-overlapping segments, with their start and end points exactly within a starting and an ending interval, respectively. The start and end points of different past life memories are within different starting and ending intervals.

The memory is like a turbulent river, with water flowing downstream, stirring rocks and sediments, constantly rising and falling. In the upper reaches, the water might be clear due to the heavy rocks; as it reaches the mouth of the river, the rocks are gradually replaced by sediments, and even a gentle breeze can stir up turbidity, entangling the memories. Each memory erosion is like a surging wave, possibly stirring up sediments or merely shifting the boulders. Numerically, matching the $i$-th starting interval contributes $a_i$, and matching the $i$-th ending interval contributes $b_i$. When these contributions reach their maximum, the "erosion" occurs. The fairies want to know the maximum value of these contributions.

If the data has 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 a single integer, the maximum total contribution.

Sample Input and Output

Input Sample #1

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

Output Sample #1

7

Input Sample #2

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

Output Sample #2

4009

Input Sample #3

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

Output Sample #3

14

Input Sample #4

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

Output Sample #4

-1

Notes/Hints

For the first sample, match the starting interval $[1,3]$ with the ending interval $[4,5]$, select the segment $[1,5]$ with length $5-1=4$, and match the starting interval $[7,8]$ with the ending interval $[9,10]$, select the segment $[7,10]$ with length $10-7=3$. The total length selected is $4+3=7$, satisfying the existence of $n$ matches between starting and ending intervals, and the selected segments do not overlap, achieving the maximum total contribution.

For the second sample, match $[1,2]$ with $[9,10]$ and $[3,5]$ with $[5,7]$, select segments $[1,10]$ and $[5,5]$.

For the third sample, match $[1,2]$ with $[3,10]$ and $[4,5]$ with $[7,7]$, select segments $[1,5]$ and $[5,7]$.

subtask1: For $15\%$ of the data, $n <= 5, m1, m2 <= 10$.

subtask2: For $100\%$ of the data, $n, m1, m2 <= 100$, all data in the problem $\le 10^3$.

见题面 Input 部分

见题面 Output 部分