P11554 [ROIR 2016] 假期旅行 (Day 1)

翻译自 [ROIR 2016 D1T4](https://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-regional-2016-day1.pdf)。

某地铁路是一条直线，沿线有 $n$ 个车站。我们称从某个车站到下一个车站之间的路段为一个区段。 一列火车从车站 $1$ 开始，最终到达车站 $n$，在每个车站都会停靠。火车上有 $k$ 个座位，座位编号从 $1$ 到 $k$。每张火车票上由三个数字 $s, t, a$，表示持有这张票的乘客允许从车站 $s$ 到车站 $t$，坐在编号为 $a$ 的座位上。 暑假的一天，Vasya 计划乘坐火车从一个车站到另一个车站。他发现当天已经售出了 $m$ 张票，并且可能在他感兴趣的车站之间已经没有空座位。直接从某个车站到另一个车站的票只能在每个区段的对应座位都空闲时购买。 Vasya 想到，有时即便如此，他仍然可以通过购买几张票，在某些中途车站换座位再继续乘坐。因此，他希望购买最少的票数，让他在每个区段都有座位。 Vasya 还没有完全确定下来要从哪个车站出发，也没有决定最终到达哪个车站。他记录了 $q$ 个出行方案，对于每个方案，他想知道如果选择这个方案，最少需要购买多少张票才能完成这次旅行。

无

无

### 样例解释 - 在车站 $2$ 到车站 $3$ 的区段，所有座位都已经被占用，因此从车站 $1$ 到车站 $5$ 的旅程无法进行。 - 从车站 $3$ 到车站 $5$，需要购买两张票：从车站 $3$ 到车站 $4$ 坐座位 $2$，从车站 $4$ 到车站 $5$ 坐座位 $1$。 - 从车站 $4$ 到车站 $5$ 只需要一张座位 $1$ 的票。 ### 数据范围 | 子任务 | 是否捆绑 | 分值 | $n,m,k\le$ | $q\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | 是 | $33$ | $100$ | $1$ | | $2$ | 是 | $30$ | $200000$ | $1$ | | $3$ | 是 | $37$ | $200000$ | $200000$ |