你作为一名市警察局局长，每天都要沿着城市的道路巡逻。这座城市共有 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(B−2),di(B−1)，表示与这条新路有关的权值。
输出仅一行，一个正整数，表示最小的耗油量。如果无法完成任务，请输出 −1-1−1。
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 101≤n≤20,1≤m≤n(n−1),1≤k≤1012,1≤A≤n(n−1),1≤B≤101≤x,y≤n,1≤c≤1031 \leq x,y \leq n,1 \leq c \leq 10^31≤x,y≤n,1≤c≤1031≤dij≤1031 \leq d_{ij} \leq 10^31≤dij≤103