TiMe Table

어떤 학생이 아침마다 타는 통학 버스에서 한 가지를 알아차렸다. 그 버스의 이용자가 늘 같은 사람들이라는 것이다. 궁금해서 버스에 타고 있는 이용자들에게 물어보니, 매일 정해진 시각에 버스 정류장에 오는 모양이었다. 그렇다면 승객에게 더 좋은 버스 시간표가 있지 않을까 하고 그 학생은 생각했다.

학생이 타는 통학로에는 버스 영업소에서 종점까지 $S$개의 버스 정류장이 일직선으로 늘어서 있다. (영업소는 버스 정류장에 포함되지 않지만, 종점은 버스 정류장에 포함된다.) 각 버스 정류장에는 영업소에서 가까운 쪽부터 차례로 $1$부터 $S$까지 번호가 붙어 있다. 영업소와 $i$번째 버스 정류장의 거리는 $x_i$이다. 버스는 먼저 영업소를 출발하고, 그로부터 $x_i$의 시간이 지난 뒤 $i$번째 버스 정류장에 도착한다. 버스 정류장에는 $N$명의 이용자가 찾아온다. $i$번째 이용자는 시각 $t_i$에 버스 정류장 $p_i$에 도착한다.

이 통학로에는 하루에 정확히 $M$대의 버스가 영업소에서 종점까지 운행한다. 버스는 정류장에 서면 그 정류장에서 기다리던 이용자를 전부 태우고 다음 정류장으로 향한다. 정류장에서 이용자를 태우는 시간은 무시할 수 있다고 가정한다. 이제 각 버스가 영업소를 출발하는 시각을 자유롭게 정할 수 있을 때, 이용자의 대기 시간 합을 최소화하려고 한다.

입력은 다음 형식으로 주어진다.

$S$ $N$ $M$

$x_1$ $...$ $x_S$

$t_1$ $p_1$

$...$

$t_N$ $p_N$

대기 시간 합의 최솟값을 한 줄에 출력한다.

• $1 ≤ S, N, M ≤ 2000$
• $1 ≤ x_1 < x_2 < …< x_S ≤ 10^4$
• $0 ≤ t_i ≤ 10^4$
• $1 ≤ p_i ≤ S$
• 입력값은 모두 정수이다.