1428: #6209. 巡逻

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

你作为一名市警察局局长,每天都要沿着城市的道路巡逻。这座城市共有 nnn 个地标,某些地标之间可能会有单向道路相连,这些道路共有 mmm 条,我们称这些单向道路为旧路。现在市里新修了 AAA 条单向道路,我们称这些单向道路为新路。每条旧路都有一个权值 ccc,表示通过这条道路消耗的油量;每条新路也有权值,也表示通过这条道路消耗的油量,不过权值是变化的。以第 iii 条新路为例,一开始其权值为 di0d_{i0}di0,若总共通过了 jjj 条新路,其权值就会变为 dijd_{ij}dij(在完全一条新路通过时才会改变)。不会存在两条旧路连接相同的两个地标,也不会存在两条新路连接相同的两个地标。
你的警察局位于城市的 111 号地标处,现在你需要通过恰好 kkk 条旧路和 BBB 条新路(都可以重复经过),并最终停在任意地标处。你希望知道完成这件任务最少需要消耗多少油。

输入格式

输入第一行为五个正整数 n,m,k,A,Bn,m,k,A,Bn,m,k,A,B,分别表示地标个数、旧路条数、需要经过的旧路条数、新路条数、需要经过的新路条数。
接下来 mmm 行,每行三个正整数 x,y,cx,y,cx,y,c,描述了一条从 xxx 指向 yyy 的旧路。
接下来 AAA 行,每行前两个正整数为 x,yx,yx,y,描述了一条从 xxx 指向 yyy 的新路。接下来 BBB 个正整数,分别为 di0,di1,…,di(B−2),di(B−1)d_{i0},d_{i1},\ldots,d_{i(B-2)} ,d_{i(B-1)}di0,di1,,di(B2),di(B1),表示与这条新路有关的权值。

输出格式

输出仅一行,一个正整数,表示最小的耗油量。如果无法完成任务,请输出 −1-11

样例

样例输入

3 3 1 1 1
1 2 1
2 3 2
3 1 1
2 3 2

样例输出

3

数据范围与提示

1≤n≤20,1≤m≤n(n−1),1≤k≤1012,1≤A≤n(n−1),1≤B≤101 \leq n \leq 20,1 \leq m \leq n(n-1),1 \leq k \leq 10^{12},1 \leq A \leq n(n-1),1 \leq B \leq 101n20,1mn(n1),1k1012,1An(n1),1B10
1≤x,y≤n,1≤c≤1031 \leq x,y \leq n,1 \leq c \leq 10^31x,yn,1c103
1≤dij≤1031 \leq d_{ij} \leq 10^31dij103