3124: GESP7级2312 商品交易
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：7
题目描述
市场上共有 种商品，编号从 至 ，其中，第 种商品价值 元。
现在共有 个商人，编号从 至 。在第 个商人这，你可以使用你手上的第 种商品交换商人手上的第 种商品。每个商人都会按照商品价值进行交易，具体来说，如果 ，他将会付给你 元钱；否则，那么你需要付给商人 元钱。除此之外，每次交易商人还会收取 元作为手续费，不论交易商品的价值孰高孰低。
你现在拥有商品 ，并希望通过一些交换来获得商品 。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）
输入
第一行四个整数 ，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 ，保证 。
第二行 个用单个空格隔开的正整数 ，依次表示每种商品的价值。保证 。
接下来 行，每行两个整数 ，表示在第 个商人这，你可以使用第 种商品交换第 种商品。保证 ，保证 。
输出
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 ，请输出
No solution。样例输入 复制
3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2样例输出 复制
5提示
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
**样例解释 1**
可以先找2 号商人，花2-1=1 元的差价以及1 元手续费换得商品1 ，再找4 号商人，花4-2 元的差价以及1元手续费换得商品2 。总计花费1+1+2+1=5 元。
**样例解释 2**
可以找2 号商人，直接换得商品2 的同时，赚取100-4=96 元差价，再支付1 元手续费，净赚95 元。
也可以先找0 号商人换取商品1 ，再找1 号商人换取商品2 ，不过这样只能赚94 元。
**数据规模**
对于30%的测试点，保证N<=10 ，M<=20 。
对于70%的测试点，保证N<=10^3^ ，M<=10^4^ 。
对于100%的测试点，保证 N<=10^5^，M<=2*10^5^