5235 - GESP:2023-12月等级7-T1-商品交易

输入

输出

输出一行一个整数,表示最少的花费。特别地,如果无法通过交换换取商品b ,请输出 No solution

样例

输入

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

输出

5

输入

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

输出

-95

输入

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

输出

No solution

提示

样例解释 1 可以先找2号商人,花2-1元的差价以及1元手续费换得商品1,再找4号商人,花4-2=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
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题