← 返回题目列表

AtCoder · awc0062_b

B. 高速公路收费站

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

分数: 333 分

问题陈述

高桥正在高速公路上行驶前往目的地。

沿着这条高速公路,有 N 收费站按顺序放置在入口和目的地之间。的 i第一个收费站距离 D_i 距离入口米。目的地距离 距入口 G 米,比所有收费站距入口更远。

高桥的车总是以匀速行驶 1 米每秒。当他到达收费站时,他必须停下来交费;在 i第一个收费站,需要 T_i 从停止到完成支付并再次出发的秒数。除了收费站外,他不会在任何地方停车。

Takahashi 有 ETC 卡,必须设置 正好一个 ETC 使用部分。具体来说,他选择一个整数 i (1 \leq i \leq N-K+1)并指定 正是 K 连续编号的收费站 i-第 (i+K-1)-th 作为 ETC 使用部分。在 K 收费站指定为ETC使用路段,可不停车通过,不产生缴费时间。在所有其他收费站,他都像往常一样停车付费。

高桥从高速公路入口到目的地所需的时间是旅行时间的总和(因为从入口到目的地的距离是 G 米,速度为 1 米每秒,这是 G 秒)以及ETC使用区间外所有收费站的总缴费时间。求最优选择ETC使用路段时可能的最小总时间。

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq G \leq 10^9
  • 1 \leq D_i < G (1 \leq i \leq N)
  • D_1 < D_2 < \cdots < D_N
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N K G
D_1 T_1
D_2 T_2
\vdots
D_N T_N
  • 第一行包含三个空格分隔的整数: N,收费站数量; K,指定为ETC使用路段的收费站数量;和 G,从入口到目的地的距离。
  • 的 (1 + i)- 第行 (1 \leq i \leq N) 包含两个空格分隔的值: D_i,距离 i从入口处算起的第一个收费站,以及 T_i,在该收费站缴费所需的时间。

输出

以单行输出高桥从高速公路入口到目的地所需的最短时间。


示例输入 1

3 2 100
10 5
30 10
60 3

示例输出 1

103

示例输入 2

5 3 1000
100 20
200 50
400 30
600 40
800 10

示例输出 2

1030

示例输入 3

7 4 500000000
1000 100000000
50000 200000000
100000 150000000
200000 300000000
300000 50000000
400000 250000000
450000 100000000

示例输出 3

900000000