P7192 [COCI 2007/2008 #6] GEORGE

T 先生来 Luka 所在的小镇玩，因为 T 先生是一个大人物，警察会对他将走过的路实行交通管制。 Luka 在镇上是一名送货的卡车司机。但是由于一些路正在进行交通管制，他无法及时交货，还因此差点丢掉了他的工作。

Luka 知道 T 先生游玩的路线，并且他想要知道最短的交货时间。 该城市由若干十字路口和连接它们的道路连接，并且 Luka 知道他需要在某条路段上开多长时间（T 先生需要同样的时间以开过该路段）。 例如，如果 T 先生在第 $10$ 分钟进入一条路，并且需要 $5$ 分钟离开这条路，那么该街道将在第 $10 \sim 14$ 分钟时被封锁。Luka可以在第 $9$ 分钟或更早的时候，也可以在第 $15$ 分钟及以后进入该道路。 编写一个程序，计算 Luka 在 T 先生到达城市后 $k$ 分钟开始开车的最短时间。

无

无

#### 数据规模及约定 对于 $100\%$ 的数据，$2 \le n \le 10^3$，$2 \le m \le 10^4$，$1 \le a, b \le n$，$0 \le k \le 10^3$，$ 0 \le g \le 10^3$。 #### 说明 - 本题满分 $60$ 分。 - 本题默认开启 O2 优化开关。 - 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T4 GEORGE，译者 @[tearing](https://www.luogu.com.cn/user/219791)。