市场上共有 种商品，编号从 至 ，其中，第 种商品价值 元。
现在共有 个商人，编号从 至 。在第 个商人这，你可以使用第 种商品交换第 种商品。每个商人都会按照商品价值进行交易，具体来说，如果 ，他将会付给你 元钱；否则，那么你需要付给商人 元钱。除此之外，每次交易商人还会收取 元作为手续费，不论交易商品的价值孰高孰低。
你现在拥有商品 ，并希望通过一些交换来获得商品 。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）
第一行四个整数 ，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 ，保证 。
第二行 个用单个空格隔开的正整数 ，依次表示每种商品的价值。保证 。
接下来 行，每行两个整数 ，表示第 个商人愿意使用第 种商品交换第 种商品。保证 ，保证 。
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 ，请输出 No solution
No solution
样例输入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
对于30%的测试点，保证 ， 。
对于70%的测试点，保证 ， 。
对于100%的测试点，保证 ，