商品交易

题目描述

市场上共有 种商品，编号从 ⾄ ，其中，第 种商品价值 元。 现在共有 个商⼈，编号从 ⾄ 。在第 个商⼈这，你可以使⽤第 种商品交换第 种商品。每个商⼈都 会按照商品价值进⾏交易，具体来说，如果 ，他将会付给你 元钱；否则，那么你需要付给商⼈ 元钱。除此之外，每次交易商⼈还会收取 元作为⼿续费，不论交易商品的价值孰⾼孰低。 你现在拥有商品 ，并希望通过⼀些交换来获得商品 。请问你⾄少要花费多少钱？（当然，这个最⼩花费也可能是 负数，这表⽰你可以在完成⽬标的同时赚取⼀些钱。）

输入格式

第⼀⾏四个整数 ，分别表⽰商品的数量、商⼈的数量、你持有的商品以及你希望获得的商品。保证 ，保证 。 第⼆⾏ 个⽤单个空格隔开的正整数 ，依次表⽰每种商品的价值。保证 。 接下来 ⾏，每⾏两个整数 ，表⽰第 个商⼈愿意使⽤第 种商品交换第 种商品。保证 ， 保证 。

输出格式

输出⼀⾏⼀个整数，表⽰最少的花费。特别地，如果⽆法通过交换换取商品 ，请输出 No solution 3.1.4 特别提醒 在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任 何提⽰信息。

样例输入 #1

3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2

样例输出 #1

5

样例输入 #2

3 3 0 2
100 2 4
0 1
1 2
0 2

样例输出 #2

-95

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。