题目背景

【图】特内里费空难（建议加载片刻再看）

【图】特内里费空难示意图

为了防止引起特内里费空难的跑道侵入事件（即MH - 严重/一般 事故征候），\(GMQ\)机场特聘请大佬您来设计一个自动管理系统，指挥飞机的滑行。

题目描述

其实以上【题目背景】中的内容都是为了获得 \(CAAC\) 改造拨款编出的理由，\(GMQ\)机场的真正目的是省运营费……

但聘请大佬您来设计一个自动管理系统是真的！

\(GMQ\)机场的滑行道网可以看作一张无向图，图中有三种结点：
1. 普通结点 共 \(N_1\) 个，按 \(1\)~\(N_1\) 自动编号
2. 停机坪结点 共 \(N_2\) 个，按 \(1\)~\(N_2\) 自动编号
3. 跑道结点 共 \(N_3\) 个，按 \(1\)~\(N_3\) 自动编号，同时会给出一个数字，表示该结点在跑道上的位置和跑道终点的距离（不考虑方向问题），简称“ 可用距离 ”

该无向图中的 每条边都有相应费用 。

现在某飞机在停机坪结点 \(S\) ,要求你找出一条终点为跑道结点 \(T\) 的路径，使得该路径上的费用之和尽可能少且跑道结点 \(T\) 的可用距离不小于飞机的起飞距离（会给出飞机的起飞距离）

注： 该路径除了 \(S\) 与 \(T\) 外的结点都应为普通结点

格式

输入格式

第一行四个整数 \(N_1\),\(N_2\),\(N_3\),\(M_1\),\(M_2\) 和 \(M_3\) ，分别表示普通结点数量，停机坪结点数量，跑道结点数量，停机坪结点到普通结点边的条数，普通结点到普通结点边的条数 和 普通结点到跑道结点边的条数

接下来 \(N_3\) 行，每行一个整数 \(Q_i\)，表示 \(i\) 号跑道结点的可用距离

接下来 \(M_1\) 行，每行三个整数 \(x\),\(y\) 和 \(k\) ，表示停机坪结点 \(x\) 与普通结点 \(y\) 之间有一条权值为 \(k\) 的无向边

接下来 \(M_2\) 行，每行三个整数 \(x\),\(y\) 和 \(k\) ，表示普通结点 \(x\) 与普通结点 \(y\) 之间有一条权值为 \(k\) 的无向边（保证 \(x \neq y\)）

接下来 \(M_3\) 行，每行三个整数 \(x\),\(y\) 和 \(k\) ，表示普通结点 \(x\) 与跑道结点 \(y\) 之间有一条权值为 \(k\) 的无向边

接下来一行，一个整数 \(T\) 表示有 \(T\) 个询问

接下来 \(T\) 行，每行两个整数 \(f\) 和 \(s\)，表示该飞机从 \(f\) 号停机坪结点出发，起飞距离为 \(s\)

Output

对于每个询问，输出一行

该行输出一个整数，表示最小的费用

若没有满足要求的路径，输出 Call CAAC or NTSB

样例

输入

7 3 3 3 6 3
2500
1750
1000
1 1 2
2 3 3
3 7 2
1 2 4
3 5 4
7 5 5
4 6 15
6 7 2
2 4 3
2 1 6
4 2 10
6 3 8
1
2 1500

输出

38

样例解释

数据范围

\(1 \leq N_1,N_2,N_3 \leq 1000\)
\(1 \leq M_1,M_2,M_3 \leq 20000\)
\(1 \leq k,Q_i,s \leq 5000000\)
\(1 \leq T \leq 100\)

提示

数据保证无自环

来源

\(gaomaoqi2022\)原创