309+

## 输入输出样例

### 输入样例 #1

8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1


### 输出样例 #1

27


### 输入样例 #2

7 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4


### 输出样例 #2

7


## 说明

**【样例解释 \#1】**

**【样例 \#3】**

**【数据范围】**

| 测试点编号 | $n \le$ | $m \le$ | $k \le$ |
|:-:|:-:|:-:|:-:|
| $1 \sim 3$ | $10$ | $20$ | $0$ |
| $4 \sim 5$ | $10$ | $20$ | $5$ |
| $6 \sim 8$ | $20$ | $50$ | $100$ |
| $9 \sim 11$ | $300$ | $1000$ | $0$ |
| $12 \sim 14$ | $300$ | $1000$ | $100$ |
| $15 \sim 17$ | $2500$ | $10000$ | $0$ |
| $18 \sim 20$ | $2500$ | $10000$ | $100$ |