题目描述

小S是农场主，他养了M只猫，雇了P位饲养员。农场中有一条笔直的路，路边有N座山，从1到N编号。第i座山与第i-1座山之间的距离是$D_i$。饲养员都住在1号山上。 有一天，猫出去玩。第i只猫去$H_i$号山玩，玩到时刻$T_i$停止，然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从1号山走到N号山，把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间，速度为1米每单位时间。饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。 例如有两座相距为1的山，一只猫在2号山玩，玩到时刻3开始等待。如果饲养员从1号山在时刻2或3出发，那么他可以接到猫，猫的等待时间为0或1。而如果他于时刻1出发，那么他将于时刻2经过2号山，不能接到当时仍在玩的猫。 你的任务是规划每个饲养员从1号山出发的时间，使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。

输入描述

第一行三个整数N,M,P； 第二行N-1个正整数$D_i$，表示第i座山与第i-1座山之间的距离是$D_i$； 接下去M行每行两个整数$H_i,T_i$。

输出描述

输出一个整数表示答案。

示例1

输入

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

输出

3

备注

输入样例 #2

17 173 68
78 7 76 46 35 2 20 16 2 48 11 65 99 97 96 65
7 1456
2 926
12 145
10 1490
4 144
16 418
17 1490
15 983
16 1406
9 814
6 971
17 315
5 1033
13 547
11 391
8 1124
2 82
13 1619
14 1201
3 1309
2 1470
14 1285
17 501
1 1315
3 814
9 205
13 1436
9 118
11 250
10 1627
15 1332
11 1481
7 884
13 449
10 209
5 572
2 338
13 1476
10 451
15 24
2 861
9 1253
9 599
5 535
9 222
2 247
14 832
17 1433
9 1499
15 1109
11 42
12 896
12 1321
13 917
12 1207
14 420
10 1008
1 266
13 1412
8 88
7 469
15 1060
6 1156
16 1095
14 1664
11 903
5 457
12 886
16 318
13 850
13 959
3 1640
4 1474
9 1562
5 1393
12 1118
3 54
9 97
11 733
10 631
17 993
2 884
14 103
14 597
13 168
9 962
17 1624
10 281
11 1044
14 127
13 1437
6 215
1 1390
4 853
3 936
14 1368
10 528
10 830
8 1589
4 1569
17 1479
14 350
1 1193
2 714
7 1181
3 514
4 24
8 1206
17 339
3 1195
6 1191
11 891
6 1284
4 238
4 800
12 1200
8 1238
12 1205
5 1027
17 1030
6 1554
13 232
1 221
1 648
17 1197
2 873
7 1221
7 92
3 1213
8 1590
10 127
15 677
13 127
1 799
10 1542
14 1659
15 790
14 212
16 1210
17 432
9 55
9 777
16 414
3 1018
12 1109
4 1211
17 1516
1 1111
10 1385
17 1284
16 926
1 1277
13 639
11 1689
13 522
4 856
5 486
5 678
6 853
11 197
4 769
12 382
11 1634
10 703
2 1020
7 295
15 922
8 1039
5 58
13 605
9 1451
13 1003
16 775

输出样例 #2

775

输入样例 #3

39 175 100
14 4 55 4 35 36 6 13 77 7 74 33 1 69 5 27 46 20 20 37 81 60 69 47 28 19 15 50 60 66 33 88 25 12 84 94 38 93
12 2823
17 2782
28 264
23 1400
29 3678
29 2507
17 1448
3 3676
21 2215
29 3862
2 282
21 3091
18 72
3 389
19 1221
20 1286
17 1313
38 918
28 106
13 850
39 143
29 1405
1 2805
25 1534
8 115
7 1633
8 3395
20 3509
4 3603
36 971
2 513
28 2938
24 439
3 1400
5 1222
12 1957
10 3540
36 3626
17 1240
20 404
6 392
12 2873
29 2760
15 3100
4 993
15 3257
34 3129
24 1902
1 3786
27 3313
20 3093
8 171
2 818
28 1277
12 1329
10 2570
38 3601
22 3073
24 3750
39 3214
32 3880
37 3077
4 2560
36 972
29 1859
5 3545
34 1326
16 3803
8 567
9 3212
18 1397
4 671
1 857
24 3693
10 1195
37 3202
37 722
27 2343
23 2451
9 3882
4 3395
1 356
27 2081
2 1886
29 1386
12 1201
9 296
2 309
14 387
11 1493
23 3704
35 304
28 1637
5 880
34 3330
25 3557
24 2346
2 2684
32 2361
15 3219
36 3681
4 3772
29 2995
15 3317
38 729
3 3045
28 1383
16 99
38 877
10 1074
36 1791
25 1512
13 1733
6 651
9 653
9 633
31 21
28 3096
24 2329
19 422
7 2849
26 3425
18 531
33 2658
35 2689
17 1597
29 412
17 787
3 3384
16 301
12 2032
3 2873
10 2473
39 2743
25 2452
17 16
16 483
39 1118
29 2676
25 2283
20 1893
6 7
18 1204
35 1289
20 1963
31 1114
38 2558
5 1361
5 1818
15 1695
19 1340
28 906
38 56
29 2455
8 3273
11 62
28 1723
20 1691
17 2566
31 2458
3 1468
22 333
23 3565
25 802
6 3537
6 379
23 3324
20 3424
17 1943
8 2001
17 3115
38 3753
27 1871
9 1428
31 1065

输出样例 #3

627

数据范围

对于全部数据，$2 \leq N \leq 10^5,1 \leq M \leq 10^5,1 \leq p \leq 100,1 \leq D_i \lt 10^4,1 \leq H_i \leq N,0 \leq T_i \leq 10^9$。