Polycarp lives on a coordinate line at the point $x = 0$. He goes to his friend that lives at the point $x = a$. Polycarp can move only from left to right, he can pass one unit of length each second.

Now it's raining, so some segments of his way are in the rain. Formally, it's raining on $n$ non-intersecting segments, the $i$-th segment which is in the rain is represented as $[l_i, r_i]$ ($0 \le l_i < r_i \le a$).

There are $m$ umbrellas lying on the line, the $i$-th umbrella is located at point $x_i$ ($0 \le x_i \le a$) and has weight $p_i$. When Polycarp begins his journey, he doesn't have any umbrellas.

During his journey from $x = 0$ to $x = a$ Polycarp can pick up and throw away umbrellas. Polycarp picks up and throws down any umbrella instantly. He can carry any number of umbrellas at any moment of time. Because Polycarp doesn't want to get wet, he must carry at least one umbrella while he moves from $x$ to $x + 1$ if a segment $[x, x + 1]$ is in the rain (i.e. if there exists some $i$ such that $l_i \le x$ and $x + 1 \le r_i$).

The condition above is the only requirement. For example, it is possible to go without any umbrellas to a point where some rain segment starts, pick up an umbrella at this point and move along with an umbrella. Polycarp can swap umbrellas while he is in the rain.

Each unit of length passed increases Polycarp's fatigue by the sum of the weights of umbrellas he carries while moving.

Can Polycarp make his way from point $x = 0$ to point $x = a$? If yes, find the minimum total fatigue after reaching $x = a$, if Polycarp picks up and throws away umbrellas optimally.


-----Input-----

The first line contains three integers $a$, $n$ and $m$ ($1 \le a, m \le 2000, 1 \le n \le \lceil\frac{a}{2}\rceil$) — the point at which Polycarp's friend lives, the number of the segments in the rain and the number of umbrellas.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \le l_i < r_i \le a$) — the borders of the $i$-th segment under rain. It is guaranteed that there is no pair of intersecting segments. In other words, for each pair of segments $i$ and $j$ either $r_i < l_j$ or $r_j < l_i$.

Each of the next $m$ lines contains two integers $x_i$ and $p_i$ ($0 \le x_i \le a$, $1 \le p_i \le 10^5$) — the location and the weight of the $i$-th umbrella.


-----Output-----

Print "-1" (without quotes) if Polycarp can't make his way from point $x = 0$ to point $x = a$. Otherwise print one integer — the minimum total fatigue after reaching $x = a$, if Polycarp picks up and throws away umbrellas optimally.


-----Examples-----
Input
10 2 4
3 7
8 10
0 10
3 4
8 1
1 2

Output
14

Input
10 1 1
0 9
0 5

Output
45

Input
10 1 1
0 9
1 5

Output
-1



-----Note-----

In the first example the only possible strategy is to take the fourth umbrella at the point $x = 1$, keep it till the point $x = 7$ (the total fatigue at $x = 7$ will be equal to $12$), throw it away, move on from $x = 7$ to $x = 8$ without an umbrella, take the third umbrella at $x = 8$ and keep it till the end (the total fatigue at $x = 10$ will be equal to $14$). 

In the second example the only possible strategy is to take the first umbrella, move with it till the point $x = 9$, throw it away and proceed without an umbrella till the end.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from functools import cmp_to_key
import sys

def getIntList():
	return list(map(int, input().split()))
(a, n, m) = getIntList()
rainend = set()
umbr = {}
keyPointSet = set([0, a])
for i in range(n):
	t = tuple(getIntList())
	for j in range(t[0] + 1, t[1] + 1):
		rainend.add(j)
	keyPointSet.add(t[1])
for i in range(m):
	t = getIntList()
	if t[0] not in umbr or t[1] < umbr[t[0]]:
		umbr[t[0]] = t[1]
	keyPointSet.add(t[0])
keyPoint = list(keyPointSet)
keyPoint.sort()
dp = {}
dp[0] = {}
dp[0][0] = 0
if 0 in umbr:
	dp[0][umbr[0]] = 0
for i in range(1, len(keyPoint)):
	x = keyPoint[i]
	lx = keyPoint[i - 1]
	ifrain = x in rainend
	dp[x] = {}
	nowdp = dp[x]
	lastdp = dp[lx]
	for z in lastdp:
		if z == 0:
			if not ifrain:
				nowdp[0] = lastdp[0]
		else:
			nowdp[z] = lastdp[z] + z * (x - lx)
	if len(nowdp) > 0:
		nowdp[0] = min(nowdp.values())
		if x in umbr:
			if umbr[x] not in nowdp or nowdp[0] < nowdp[umbr[x]]:
				nowdp[umbr[x]] = nowdp[0]
	else:
		print(-1)
		return
print(min(dp[a].values()))


import sys
(a, m, n) = list(map(int, input().split()))
aux = [0] * (a + 1)
inf = 10 ** 15
dp = [aux.copy() for i in range(n + 1)]
m1 = 10 ** 12
m2 = 10 ** 12
for i in range(m):
	(l, r) = list(map(int, input().split()))
	if l < m1:
		m1 = l
	for j in range(l, r):
		dp[0][j + 1] = inf
s = []
for i in range(1, n + 1):
	(x, w) = list(map(int, input().split()))
	s.append(tuple([x, w]))
	if x < m2:
		m2 = x
if m2 > m1:
	print(-1)
	sys.exit()
s.sort()
for i in range(1, n + 1):
	x = s[i - 1][0]
	w = s[i - 1][1]
	for j in range(x + 1):
		dp[i][j] = dp[i - 1][j]
	for j in range(x + 1, a + 1):
		if i != 1:
			dp[i][j] = min(dp[0][j] + dp[i][j - 1], dp[i - 1][j], w * (j - x) + dp[i][x])
		else:
			dp[i][j] = min(dp[0][j] + dp[i][j - 1], w * (j - x) + dp[i][x])
ans = dp[-1][-1]
if ans >= inf:
	print(-1)
else:
	print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def input_l():
	return map(int, input().split())

def input_t():
	return tuple(input_l())

def main():
	(a, s, d) = input_l()
	q = []
	e = []
	z = [0] * (a + 1)
	for i in range(s):
		w = input_t()
		for k in range(w[0], w[1]):
			q.append(k + 1)
	for j in range(d):
		e.append(input_t())
	e = sorted(e, key=lambda x: x[0])
	if e[0][0] > q[0] - 1:
		print(-1)
		sys.exit(0)
	for i in range(1, len(z)):
		if i not in q:
			z[i] = z[i - 1]
			continue
		for j in e:
			if i >= j[0]:
				c = (i - j[0]) * j[1] + z[j[0]]
				if z[i] > 0:
					if c < z[i]:
						z[i] = c
				else:
					z[i] = c
	print(z[-1])
main()


import math

def main():
	(a, n, m) = map(int, input().split())
	rain = []
	u = []
	w = []
	raining = [False] * (a + 1)
	for i in range(n):
		(l, r) = map(int, input().split())
		rain.append((l, r))
		for j in range(l, r):
			raining[j] = True
	for i in range(m):
		(x, y) = map(int, input().split())
		u.append(x)
		w.append(y)
	rain_int = [0] * a
	for i in range(n):
		rain_int[rain[i][0] - 1] = 1
		rain_int[rain[i][1] - 1] = -1
	umbrellas = [-1 for _ in range(a + 1)]
	for (i, x) in enumerate(u):
		if umbrellas[x] == -1 or w[umbrellas[x]] > w[i]:
			umbrellas[x] = i
	dp = [[math.inf for _ in range(m + 1)] for _ in range(a + 1)]
	dp[0][m] = 0
	for i in range(a):
		for j in range(m + 1):
			if dp[i][j] == math.inf:
				continue
			if not raining[i]:
				dp[i + 1][m] = min(dp[i + 1][m], dp[i][j])
			if j < m:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + w[j])
			if umbrellas[i] != -1:
				dp[i + 1][umbrellas[i]] = min(dp[i + 1][umbrellas[i]], dp[i][j] + w[umbrellas[i]])
	ans = math.inf
	for i in range(m + 1):
		ans = min(ans, dp[a][i])
	print(-1 if ans == math.inf else ans)
main()


import sys
(a, n, m) = list(map(int, input().split(' ')))
seg = []
for i in range(n):
	rained = tuple(map(int, input().split(' ')))
	for k in range(rained[0], rained[1]):
		seg.append(k + 1)
umbrella = []
for j in range(m):
	u = tuple(map(int, input().split(' ')))
	umbrella.append(u)
memo = [0] * (a + 1)
umbrella = sorted(umbrella, key=lambda x: x[0])
if umbrella[0][0] > seg[0] - 1:
	print(-1)
	return
for index in range(1, len(memo)):
	if index not in seg:
		memo[index] = memo[index - 1]
		continue
	for each in umbrella:
		if index >= each[0]:
			cur = (index - each[0]) * each[1] + memo[each[0]]
			if memo[index] > 0:
				if cur < memo[index]:
					memo[index] = cur
			else:
				memo[index] = cur
print(memo[-1])


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop, heapify
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import lru_cache
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
sys.setrecursionlimit(10 ** 6)
(a, n, m) = li()
l = []
rain = defaultdict(int)
for i in range(n):
	(c, b) = li()
	for j in range(c, b):
		rain[j, j + 1] = 1
umbrellas = [float('inf')] * (a + 5)
for i in range(m):
	(c, b) = li()
	umbrellas[c] = min(umbrellas[c], b)

@lru_cache(None)
def dp(i=0, umbon=0):
	if i == a:
		if rain[i - 1, i]:
			if umbon:
				return umbon
			return float('inf')
		else:
			return umbon
	else:
		ans = float('inf')
		last = umbon
		if rain[i - 1, i]:
			umbon = min(umbon, umbrellas[i]) if umbon else umbrellas[i]
			if not last:
				last = float('inf')
			ans = min(ans, last + dp(i + 1, umbon))
			ans = min(ans, last + dp(i + 1, 0))
		else:
			ans = min(ans, dp(i + 1, 0) + last)
			umbon = min(umbon, umbrellas[i]) if umbon else umbrellas[i]
			ans = min(ans, dp(i + 1, umbon) + last)
	return ans
print(dp(0, 0) if dp(0, 0) != float('inf') else -1)


from sys import stdin, stdout
from math import gcd, ceil, sqrt
from collections import Counter
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
(a, n, m) = iia()
rain = []
for _ in range(n):
	(l, r) = iia()
	for i in range(l, r):
		rain.append(i)
umb = []
for _ in range(m):
	umb.append(iia())
rain.sort()
umb.sort()
dp = [0] * (a + 1)
for i in range(a + 1):
	if i not in rain:
		if i != 0:
			dp[i] = dp[i - 1]
	else:
		for j in umb:
			if j[0] <= i:
				temp = (i + 1 - j[0]) * j[1]
				if j[0] - 1 >= 0:
					temp += dp[j[0] - 1]
				if dp[i] > 0:
					dp[i] = min(dp[i], temp)
				else:
					dp[i] = temp
			else:
				break
if umb[0][0] > rain[0]:
	print(-1)
else:
	print(dp[-1])


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
INF = 10 ** 15

def dp_min(dp, pos, new_val):
	if pos not in dp:
		dp[pos] = new_val
	else:
		dp[pos] = min(dp[pos], new_val)

def solve():
	(a, n, m) = list(map(int, input().split()))
	has_rain = [False] * a
	for _ in range(n):
		(l, r) = map(int, input().split())
		for i in range(l, r):
			has_rain[i] = True
	umbrella = [INF] * a
	for _ in range(m):
		(x, p) = map(int, input().split())
		if x == a:
			continue
		umbrella[x] = min(umbrella[x], p)
	dp = {-1: 0}
	for i in range(a):
		new_dp = {}
		for (umbrella_weight, best_cost) in dp.items():
			if not has_rain[i]:
				dp_min(new_dp, -1, best_cost)
			dp_min(new_dp, umbrella[i], best_cost + umbrella[i])
			if umbrella_weight != -1:
				dp_min(new_dp, umbrella_weight, best_cost + umbrella_weight)
		dp = new_dp
	best = min(dp.values())
	if best >= INF:
		print(-1)
	else:
		print(best)
t = 1
for _ in range(t):
	solve()


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
MOD = 10 ** 9 + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(a, s, d) = map(int, input().split())
q = []
e = []
z = [0] * (a + 1)
for i in range(s):
	w = tuple(map(int, input().split()))
	for k in range(w[0], w[1]):
		q.append(k + 1)
for j in range(d):
	e.append(tuple(map(int, input().split())))
e = sorted(e, key=lambda x: x[0])
if e[0][0] > q[0] - 1:
	print(-1)
	exit()
for i in range(1, a + 1):
	if i not in q:
		z[i] = z[i - 1]
		continue
	for j in e:
		if i >= j[0]:
			c = (i - j[0]) * j[1] + z[j[0]]
			if z[i] > 0:
				if c < z[i]:
					z[i] = c
			else:
				z[i] = c
print(z[-1])


rd = lambda : map(int, input().split())
(a, n, m) = rd()
s = set()
u = {}
k = set([0, a])
for _ in range(n):
	(l, r) = rd()
	for x in range(l + 1, r + 1):
		s.add(x)
	k.add(r)
for _ in range(m):
	(x, p) = rd()
	u[x] = min(p, u.get(x, 1000000000.0))
	k.add(x)
k = sorted(list(k))
dp = {}
dp[0] = {}
dp[0][0] = 0
if 0 in u:
	dp[0][u[0]] = 0
for i in range(1, len(k)):
	x = k[i]
	y = k[i - 1]
	dp[x] = {}
	for z in dp[y]:
		if z:
			dp[x][z] = dp[y][z] + z * (x - y)
		elif x not in s:
			dp[x][0] = dp[y][0]
	if len(dp[x]):
		dp[x][0] = min(dp[x].values())
		if x in u:
			if u[x] not in dp[x] or dp[x][0] < dp[x][u[x]]:
				dp[x][u[x]] = dp[x][0]
	else:
		print(-1)
		exit()
print(dp[a][0])


import sys
from collections import deque, defaultdict, namedtuple
from math import sqrt, factorial, gcd, ceil, atan, pi

def input():
	return sys.stdin.readline()[:-1]
import string
import operator
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1000000000.0) + 7
INF = float('inf')

def solve():
	(a, n, m) = [int(x) for x in input().split()]
	rain = [0] * (a + 1)
	for _ in range(n):
		(l, r) = [int(x) for x in input().split()]
		for i in range(l + 1, r + 1):
			rain[i] = 1
	umb = []
	for _ in range(m):
		(x, p) = [int(x) for x in input().split()]
		umb.append((x, p))
	umb.sort()
	dp = [INF for _ in range(a + 1)]
	dp[0] = 0
	for i in range(1, a + 1):
		if rain[i]:
			for (x, p) in umb:
				if x >= i:
					break
				dp[i] = min(dp[i], dp[x] + p * (i - x))
		else:
			dp[i] = dp[i - 1]
	if dp[a] == INF:
		print(-1)
	else:
		print(dp[a])
t = 1
for case in range(1, t + 1):
	ans = solve()