#P12380. [蓝桥杯 2023 省 Python B] 管道

[蓝桥杯 2023 省 Python B] 管道

题目描述

有一根长度为 lenlen 的横向的管道,该管道按照单位长度分为 lenlen 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的,位于 LiL_i 的阀门会在 SiS_i 时刻打开,并不断让水流入管道。

对于位于 LiL_i 的阀门,它流入的水在 Ti(TiSi)T_i (T_i \geq S_i) 时刻会使得从第 Li(TiSi)L_i - (T_i - S_i) 段到第 Li+(TiSi)L_i + (T_i - S_i) 段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n,lenn, len,用一个空格分隔,分别表示会打开的阀门数和管道长度。

接下来 nn 行每行包含两个整数 Li,SiL_i, S_i,用一个空格分隔,表示位于第 LiL_i 段管道中央的阀门会在 SiS_i 时刻打开。

输出格式

输出一行包含一个整数表示答案。

3 10
1 1
6 5
10 2
5

提示

评测用例规模与约定

  • 对于 30%30\% 的评测用例,n200n \leq 200Si,len3000S_i, len \leq 3000
  • 对于 70%70\% 的评测用例,n5000n \leq 5000Si,len105S_i, len \leq 10^5
  • 对于所有评测用例,1n1051 \leq n \leq 10^51Si,len1091 \leq S_i, len \leq 10^91Lilen1 \leq L_i \leq lenLi1<LiL_{i-1} < L_i