配点: 100 点
問題
IOI 国有城镇 1 从城镇 N 最多 N 个城镇组成,城镇之间由道路连接。IOI 国有 K 条道路,所有道路都连接着不同的 2 个城镇。汽车可以在道路上双向自由行驶,但不能通过道路以外的地方从一个城镇前往另一个城镇。
IOI 国的城镇 1 居住在城镇的 JOI 君,决定乘出租车前往居住在城镇的祖母家。IOI 国有出租车公司 N 乘出租车前往祖母家。IOI 国有出租车公司 1 出租车公司 N 最多 N 个出租车公司。IOI 国的出租车公司有如下稍微特殊的规定。
- 出租车公司 i 的出租车中,城镇 i 只能在……乘车。
- 出租车公司 i 出租车的车费,无论乘坐的距离如何 C_i 都是……。
- 出租车公司 i 出租车在乘车后连续最多 R_i 条道路。
例如 R_1 = 2 在……的情况下,如果在城镇 1 出租车公司 1 乘坐出租车,最多只能通行 2 条道路,因此为了通行至少 3 条道路,需要在中途的城镇换乘出租车。
打飞机君不能在城镇以外的地点乘坐出租车,也不能在城镇以外的地点下出租车。此外,也不能使用出租车以外的移动手段。请编写程序,求出 JOI 君到达城镇 N 所需车费总和的最小值。
入力
输入由 1 + N + K 行组成。
1 第 行中, 2 整数 N, K (2 \leqq N \leqq 5\,000,N - 1 \leqq K \leqq 10\,000) 以空格分隔给出。这表示 IOI 国由 N 个城镇组成,且 IOI 国的道路数为 K 条。
继续 N 在行中的 i 行目 (1 \leqq i \leqq N) 中,2 整数 C_i, R_i (1 \leqq C_i \leqq 10\,000,1 \leqq R_i \leqq N) 以空格分隔给出。这表示出租车公司 i 的出租车运费为 C_i ,最大 R_i 表示仅可使用主干道。
继续 K 在行中的 j 行目 (1 \leqq j \leqq K) 有不同 2 整数 A_j, B_j (1 \leqq Aj < Bj \leqq N)以空格作为分隔符。这是一个小镇 A_j 和镇 表示 B_j 之间有一条路。一样 集合 (A_j, B_j) 是 它从未被写入超过 2 次。
给定输入数据,保证您可以从任何城镇乘坐出租车到任何其他城镇。
出力
JOI 君美镇 一个整数,表示前往 1 从城镇 N 所需的最低总票价。 输出为 1 行。
入力例 1
6 6 400 2 200 1 600 3 1000 1 300 5 700 4 1 2 2 3 3 6 4 6 1 5 2 4
出力例 1
700
上面的输入/输出示例对应于下图。圆圈代表城镇,线条代表道路。

在此输入/输出示例中,JOI 要到达 6 ,请执行以下操作。
町 1 乘出租车去镇上
转至 5 。 (票价 400)
町 5 乘出租车去镇上
转至 6 。 (票价 300)
JOI 如果您走这条路线,总票价为 400 + 300 = 700 ,所以
输出700 。