#8133. 「GESP23.12七级」T1商品交易 入门

时间限制:1000 ms 内存限制:1 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

市场上共有 种商品,编号从 ,其中,第 种商品价值 元。

现在共有 个商人,编号从 。在第 个商人这,你可以使用第 种商品交换第 种商品。每个商人都会按照商品价值进行交易,具体来说,如果 ,他将会付给你 元钱;否则,那么你需要付给商人 元钱。除此之外,每次交易商人还会收取 元作为手续费,不论交易商品的价值孰高孰低。

你现在拥有商品 ,并希望通过一些交换来获得商品 。请问你至少要花费多少钱?(当然,这个最小花费也可能是负数,这表示你可以在完成目标的同时赚取一些钱。)

输入格式

第一行四个整数 ,分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 ,保证

第二行 个用单个空格隔开的正整数 ,依次表示每种商品的价值。保证

接下来 行,每行两个整数 ,表示第 个商人愿意使用第 种商品交换第 种商品。保证 ,保证

输出格式

输出一行一个整数,表示最少的花费。特别地,如果无法通过交换换取商品 ,请输出 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%的测试点,保证