쓰기

글을 쓰는 Bjarki

Bjarki는 $n$글자로 이루어진 단어를 쓰려고 한다. Bjarki는 어떤 단어를 쓸지 아직 정하지 않았지만, 그 단어가 $m$개의 서로 다른 글자로 이루어져 있고, $i$번째 글자가 단어에 $a_i$ 번 등장하며, 이 글자 하나를 지우는 데 지우개가 $b_i$밀리그램 필요하다는 것은 알고 있다.

하지만 Bjarki는 지우개를 모두 집에 두고 와서 곤란한 상황에 빠졌다. 그래서 친구 Unnar에게 자신을 위해 A4에 가서 지우개를 사 달라고 부탁한다. Unnar는 마음씨가 매우 착한 소년이어서 부탁을 받아들이고 A4로 간다. A4로 가는 길에 Unnar는 Bjarki가 얼마나 많이 지울지 모른다는 사실을 깨닫고 완전히 당황한다. 그래서 먼저 점술가 Didda를 찾아가 물어보기로 한다.

점술가 Didda는 신비로운 여성이다. 그녀는 Unnar에게 Bjarki의 글쓰기를 $Q$개의 연산으로 나타낼 수 있으며, 각 연산은 두 정수 $x_i,y_i$로 이루어진다고 말했다. $x_i = 1$이면 Bjarki가 $y_i$개의 글자를 쓴다는 뜻이고, $x_i = 2$이면 Bjarki가 마지막 $y_i$개의 글자를 지운다는 뜻이다. 기뻐진 Unnar는 밖으로 뛰어나가 다시 A4로 향하지만, 이제 이런 생각이 든다. 이 $Q$개의 연산으로 나타낼 수 있는, Bjarki가 쓰고 있을 가능성이 있는 모든 문자열 중에서 Bjarki에게 필요할 수 있는 지우개의 최대량은 얼마일까?

이제 Unnar는 이 모든 정보를 가지고 당신에게 전화해 도움을 요청한다. Unnar는 지우개를 몇 밀리그램 사야 하는가?

점수

그룹 | 점수 | 제한

1 | 3 | $1 \le n,m,q \le 10, x_i = 1$

2 | 7 | $1 \le n,q \le 10, m = 1$

3 | 10 | $1 \le n,q \le 20, m = 2$

4 | 10 | $1 \le n,m,q \le 100$

5 | 15 | $1 \le n,m,q \le 1\,000$

6 | 25 | $1 \le n \le 10^5$

7 | 30 | 추가 제한 없음

입력의 첫 줄에는 세 정수 $1 \le n \le 10^9, 1 \le m,q \le 10^5$가 주어진다. 다음 $m$개의 줄에는 각각 두 정수 $1 \le a_i \le n, 1 \le b_i \le 10^4$가 주어진다. 다음 $q$개의 줄에는 각각 두 정수 $1 \le x_i \le 2, 1 \le y_i \le n$가 주어진다.

모든 $a_i$의 합은 항상 $n$임이 보장된다. Bjarki는 단어에 있는 글자 수보다 더 많은 글자를 쓰지 않는다. 또한 Bjarki는 지금까지 쓴 글자 수보다 더 많은 글자를 지우지 않는다.

Unnar가 지우개를 충분히 확보하려면 몇 밀리그램을 사야 하는지 나타내는 수 하나를 출력한다. 정답은 절대로 $10^{18}$보다 크지 않다.