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