RN is playing a music game called "Mu5Ed4sH" on her computer.
Hold is a type of note with a time range $$$[l_i, r_i]$$$, and you need to keep one finger on it within the time range.
To simplify the statement, let's assume that Hold is the only type of note in the game.
In this game, the notes will appear on two tracks, forming two sequences of time ranges $$$s$$$ and $$$t$$$. If two Holds appear at the same time, then you need to use two fingers together.
However, if you use two fingers together for $$$t$$$ seconds, then you will lose exactly $$$t$$$ energy.
Given the initial energy $$$E$$$ you have, determine whether the energy is enough to play the entire game. If it is enough, output the energy you will have left.
The first line contains two integers $$$n$$$, $$$m$$$, $$$E$$$ $$$(1 \leq n + m \leq 10 ^ 5, \min(n, m) \geq 1, 0 \leq E \leq 10 ^ 9)$$$, denoting the number of time ranges in sequence $$$s$$$ and $$$t$$$, and the initial energy you have.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$${l_s}_i$$$, $$${r_s}_i$$$ $$$(0 \leq {l_s}_i \lt {r_s}_i \leq 10 ^ 9)$$$, denoting the time range of the $$$i$$$-th Hold in sequence $$$s$$$.
The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$${l_t}_i$$$, $$${r_t}_i$$$ $$$(0 \leq {l_t}_i \lt {r_t}_i \leq 10 ^ 9)$$$, denoting the time range of the $$$i$$$-th Hold in sequence $$$t$$$.
It's guaranteed that no two time ranges will overlap in the same sequence.
If the energy is not enough, print $$$-1$$$; Otherwise, print a single integer $$$x$$$, denoting the energy you will have left.
3 2 6165 70 48 92 67 10
612
1 1 9982443530 10000000000 1000000000
-1
In the first test case, there are $$$3$$$ time ranges in the first track and $$$2$$$ time ranges in the second track.
Figure of Test Case $$$1$$$ As the figure shows, during $$$[2, 4]$$$, $$$[5, 6]$$$, $$$[8, 9]$$$, you need to use two fingers. And you will lose $$$(4 - 2) + (6 - 5) + (9 - 8) = 4$$$ energy.
It can be shown that the energy is enough, and the energy you will have left is $$$616 - 4 = 612$$$.
