AT_abc024_c.[ABC024C] 民族大移動

题意简述

高桥君的王国有 $N$ 个城市，每个城市用编号 $1$ ~ $N$ 表示。

高桥国有 $K$ 个民族居住，第 $i$ 个民族生活在编号为 $S_i$ 的城市。

高桥国有百年一度的所有民族共同习俗民族大迁徙，但由于交通拥堵，所以设置了第 $i$ 天只能在编号在 $L_i$ 到 $R_i$ 的城市来来去去的限制，并最多花费 $D$ 天进行。

每个民族都遵守这一行动限制，在经过几个城市的同时前往目的地城市。

第 $i$ 个民族的目的地是 $T_i$ ，每个民族都希望尽可能早的到达目的地。

求每个民族最早到达目的地的时间。

第一行有 $3$ 个整数，分别为高桥国城市的个数 $N$ ，大迁徙的时间 $D$，高桥国所住的民族数 $K$。

接下来的 $D$ 行，有 $2$ 个整数 $L_i,R_i$，表示第 $i$ 天可来来去去的城市编号范围。

接下来的 $K$ 行，每行 $2$ 个整数 $S_i,T_i$，表示第 $i$ 个民族原本居住的城市编号和目的地城市编号。

共 $K$ 行，每行一个整数表示第 $i$ 个民族到达目的地的最少天数。

数据保证每个民族 $D$ 天内能到达目的地。