题目描述

你作为一名市警察局局长，每天都要沿着城市的道路巡逻。这座城市共有 $n$ 个地标，某些地标之间可能会有单向道路相连，这些道路共有 $m$ 条，我们称这些单向道路为旧路。现在市里新修了 $A$ 条单向道路，我们称这些单向道路为新路。每条旧路都有一个权值 $c$，表示通过这条道路消耗的油量；每条新路也有权值，也表示通过这条道路消耗的油量，不过权值是变化的。以第 $i$ 条新路为例，一开始其权值为 $d{i0}$，若总共通过了 $j$ 条新路，其权值就会变为 $d{ij}$（在完全一条新路通过时才会改变）。不会存在两条旧路连接相同的两个地标，也不会存在两条新路连接相同的两个地标。
你的警察局位于城市的 $1$ 号地标处，现在你需要通过恰好 $k$ 条旧路和 $B$ 条新路（都可以重复经过），并最终停在任意地标处。你希望知道完成这件任务最少需要消耗多少油。

输入格式

输入第一行为五个正整数 $n,m,k,A,B$，分别表示地标个数、旧路条数、需要经过的旧路条数、新路条数、需要经过的新路条数。
接下来 $m$ 行，每行三个正整数 $x,y,c$，描述了一条从 $x$ 指向 $y$ 的旧路。
接下来 $A$ 行，每行前两个正整数为 $x,y$，描述了一条从 $x$ 指向 $y$ 的新路。接下来 $B$ 个正整数，分别为 $d{i0},d{i1},\ldots,d{i(B-2)} ,d{i(B-1)}$，表示与这条新路有关的权值。

输出格式

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

样例

input

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

output

3

数据范围与提示

$1 \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 10$
$1 \leq x,y \leq n,1 \leq c \leq 10^3$
$1 \leq d_{ij} \leq 10^3$