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