Class Representative Witch
Time limit2sMemory limit512 MB
Each thread runs from the witch outward; given the held endpoint distance si, the far endpoint distance ti, and all cut distances pi, find the total length of thread left after every cut.
- Level
Medium4 of 10
- Topics
- Sorting, Binary search, Implementation, Math
- Solved
- No attempts yet
Problem
The class representative witch PATRICIA spins spider-like threads and lives inside a barrier. Her familiar MATHIEU pulls the threads she spins and flies freely through the sky. Each thread is treated as a line segment in space.
Akemi Homura tried to attack the class representative witch, but mistook a firework ball for a bomb and threw it in. As a result, on every thread the part at distance p1,…,pM from the witch was cut. Before the firework ball was thrown, for each thread the 2 endpoints of the thread and the witch lay on one line in that order, and the familiar was pulling one of the endpoints. The explosion cut the thread, and only the part the familiar held and every other part from there remained; the rest of the thread vanished.
Homura wants information about the remaining threads in order to plan her next strategy. Find the total length of the remaining threads.
Input
The input is given in the following format.
N M
s1 t1
…
sN tN
p1
…
pM
N is the number of threads in space, and M is the number of cut positions on the threads caused by the firework ball.
si,ti describe a thread: si is the distance from the witch to the endpoint the familiar was pulling, and ti is the distance from the witch to the other endpoint.
pi describes a position cut by the firework ball.
Output
Print the total length of the threads remaining after the firework ball was thrown, on one line.
Constraints
1≤N≤1051≤M≤1051≤si≤1091≤ti≤1091≤pi≤109- All input values are integers.
s1,…,sN,t1,…,tN,p1,…,pMare all distinct.