SP14821 TLIGHTS - Traffic Lights

吉姆-鲍勃住在一个有些奇怪的城市，在这里，街道不按常规方式南北或东西延伸，而是看似随机地分布着。共有 $N$（$1 \leq N \leq 10^5$）条街道，这些街道有的通过桥梁交叉，总共交汇于 $K$（$1 \leq K \leq 1000$）个路口。每个路口处除了有几条街道交汇之外，还有一个交通灯。 第 $i$ 条街道从路口 $s_i$（$1 \leq s_i \leq K$）开始，在另一个不同的路口 $e_i$（$1 \leq e_i \leq K$）结束，中间不经过其他路口。沿这条街行驶需要 $t_i$（$1 \leq t_i \leq 1000$）分钟（这个时间由街道长度、坑洼状况和路况等因素决定）。每条街道均能双向行驶，所用时间相同。 城市中的交通灯也非常特别。每个交通灯只在绿色和红色之间交替变换。而且，每个路口的交通灯绿灯和红灯持续时间不同——路口 $i$ 的交通灯绿灯持续 $g_i$（$1 \leq g_i \leq 1000$）分钟，然后红灯持续 $r_i$（$1 \leq r_i \leq 1000$）分钟，如此循环往复。 吉姆-鲍勃严格遵守交通规则，绝不会闯红灯。如果他在绿灯时到达路口，就可以直接通过；如果赶到时是红灯，他则必须等待到绿灯亮起；如果正好在灯变红的瞬间到达，他也需要等待。通过路口是不耗费时间的，因此在他穿过路口时，灯不会变为红色。 吉姆-鲍勃从自己的家（即路口 $1$）出发。他一出门，所有交通灯即刻变为绿灯，开启它们的绿-红循环。吉姆-鲍勃希望以最快速度开车去到比利-鲍勃的家（在路口 $K$）。出发和到达的路口没有交通灯，因此前述 $g$ 和 $r$ 值在这两处为 0。请计算从吉姆-鲍勃家到比利-鲍勃家所需的最少时间。

第 $1$ 行：两个整数 $N$ 和 $K$，分别表示街道数量和交叉路口数量。 接下来的 $N$ 行，每行包含三个整数 $s_i$、$e_i$ 和 $t_i$，表示第 $i$ 条街道的起点、终点以及所需时间。 接下来的 $K$ 行，每行包含两个整数 $g_i$ 和 $r_i$，表示每个交叉口的绿灯和红灯时间。

输出一个整数——表示吉姆-鲍勃从家到比利-鲍勃家所需的最短时间（分钟表示）。题目保证始终可以到达目的地。 **本翻译由 AI 自动生成**