비와 우산

Polycarp는 좌표 직선 위의 점 x = 0에 산다. 그는 점 x = a에 사는 친구에게 간다. Polycarp는 왼쪽에서 오른쪽으로만 이동할 수 있으며, 매초 길이 한 단위를 이동할 수 있다.

지금은 비가 내리고 있어 이동 경로의 일부 구간에는 비가 내린다. 형식적으로, 서로 교차하지 않는 n개의 구간에 비가 내리며, 비가 내리는 i-th번째 구간은 [$l_i$, $r_i$] (0 ≤ $l_i$ < $r_i$ ≤ a)로 나타낸다.

직선 위에는 m개의 우산이 놓여 있다. i-th번째 우산은 점 $x_i$ (0 ≤ $x_i$ ≤ a)에 있으며 무게는 $p_i$이다. Polycarp는 여정을 시작할 때 우산을 하나도 가지고 있지 않다.

점 x = 0에서 x = a까지 이동하는 동안 Polycarp는 우산을 집거나 버릴 수 있다. Polycarp는 우산을 즉시 집고 즉시 내려놓는다. 그는 어느 순간이든 원하는 수의 우산을 들고 있을 수 있다. Polycarp는 젖고 싶지 않으므로, 구간 $[x, x + 1]$에 비가 내리는 경우 (i.e. if there exists some i such that $l_i$ ≤ x and x + 1 ≤ $r_i$), x에서 x + 1로 이동하는 동안 적어도 하나의 우산을 들고 있어야 한다.

위 조건이 유일한 요구 사항이다. 예를 들어, 비가 내리는 어떤 구간이 시작되는 점까지 우산 없이 이동한 뒤 그 점에서 우산을 집고 우산을 든 채 이동할 수 있다. Polycarp는 비가 내리는 동안 우산을 바꿀 수 있다.

길이 한 단위를 이동할 때마다, 이동하는 동안 Polycarp가 들고 있는 우산들의 무게 합만큼 피로도가 증가한다.

Polycarp가 점 x = 0에서 점 x = a까지 이동할 수 있는가? 이동할 수 있다면, Polycarp가 우산을 최적으로 집고 버릴 때 x = a에 도착한 후의 최소 총 피로도를 구한다.

첫 번째 줄에 세 정수 a, n 및 m (1 ≤ a, m ≤ 2000, 1 ≤ n ≤ ⌈a/2⌉)가 주어진다. 각각 Polycarp의 친구가 사는 점, 비가 내리는 구간의 수, 우산의 수를 나타낸다.

다음 n개의 각 줄에는 두 정수 $l_i$와 $r_i$ (0 ≤ $l_i$ < $r_i$ ≤ a)가 주어지며, 이는 비가 내리는 i-th번째 구간의 경계를 나타낸다. 서로 교차하는 구간의 쌍이 없음이 보장된다. 다시 말해, 각 구간 쌍 i와 j에 대해 $r_i$ < $l_j$ 또는 $r_j$ < $l_i$ 중 하나가 성립한다.

다음 m개의 각 줄에는 두 정수 $x_i$와 $p_i$ (0 ≤ $x_i$ ≤ a, 1 ≤ $p_i$ ≤ $10^5$)가 주어지며, 이는 i-th번째 우산의 위치와 무게를 나타낸다.

Polycarp가 점 x = 0에서 점 x = a까지 이동할 수 없다면 "-1"를 따옴표 없이 출력한다. 그렇지 않으면 Polycarp가 우산을 최적으로 집고 버릴 때 x = a에 도착한 후의 최소 총 피로도를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 가능한 유일한 전략은 점 x = 1에서 네 번째 우산을 집어 점 x = 7 (the total fatigue at x = 7 will be equal to 12)까지 들고 간 뒤 버리고, x = 7에서 x = 8까지 우산 없이 이동한 다음, x = 8에서 세 번째 우산을 집어 끝까지 들고 가는 것이다 (the total fatigue at x = 10 will be equal to 14).

두 번째 예제에서 가능한 유일한 전략은 첫 번째 우산을 집어 점 x = 9까지 들고 이동한 뒤 버리고, 끝까지 우산 없이 이동하는 것이다.