小K是一个挂B，他很喜欢开挂，但是有一天，他的挂坏了，这让他很是头疼。

小K在下飞行棋，棋盘是一行共n个格子，编号依次为1~n。小K有外挂，所以他会通过外挂来前进，他共有m个外挂，第i个外挂能让他从第li格瞬移到第ri格，并花费 的 1时间，并且小K很D，所以他不需要外挂就能往回走（即从第i格走到第i - 1格，且往回走不需要时间）。

但是小K的 rp 不太好，现在发生了 q 次事件，每次事件中，小K的某一个挂会坏（这次事件结束后又会恢复），而你需要帮他求出此时他从 s 走到 t 要花费的最小时间。