← 返回题目列表

AtCoder · icpc2013summer_day2_d

D. 计时表

中文机器翻译题面 查看原题

一名学生在早上乘坐他经常乘坐的校车时注意到了一些东西。 公共汽车的使用者总是相同的。 我好奇地询问了公交车上的乘客,他们似乎每天都会在固定的时间来到公交车站。 然后,学生想,也许会有更好的公交时刻表供乘客使用。

学生上学的路线包括从公交车站到终点站的路线。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
  • 所有输入值均为整数。

入出力例

入力例 1

2 2 1
1 5
0 1
0 2

出力例 1

4

入力例 2

2 3 2
1 15
0 1
5 1
5 2

出力例 2

5
在本例中,我们将总线设置为 最好在 -10 和 4 出发。

入力例 3

4 8 1
6 38 105 390
14 1
4 2
39 3
89 2
32 4
1 1
25 1
60 4

出力例 3

1123