4022. 批发市场

【题目描述】

批发市场中有 $n$ 种商品，第$i$种商品每件的批发价为 $a_i$，批发后售出时的售价为 $b_i$ 。因为有的商品不好售卖，所以批发市场制定了批发规则：部分商品需要和其他商品捆绑批发。例如，有三个商品 $A,B,C$ 捆绑批发，如果批发$10$ 件 $A$，那么必须同时批发 $10$ 件商品 $B$ 和 $10$ 件商品 $C$ 。

现在你有$k$元钱，请问如何批发商品使得自己的利润最高？

【输入格式】

第一行三个整数 $n,m,k$ ，分别表示商品种类、捆绑关系数和总钱数。

接下来 $n$ 行，每行有两个空格隔开的整数 $a_i,b_i$，分别表示第$i$种商品的单件批发价和售价。

接下来 $m$ 行，每行有两个空格隔开的整数 $x,y$ ，表示商品 $x$ 和商品 $y$ 要捆绑批发。

【输出格式】

一行一个整数，表示获得的最高利润。

【样例1输入】

4 1 10
2 3
2 3
1 3
4 8
2 3

【样例1输出】

10

【样例1说明】

第 $2$ 种商品和第 $3$ 种商品需要捆绑批发。

批发方案为：批发第 $2$ 种商品 $2$ 件、第 $3$ 种商品 $2$ 件、第 $4$ 种商品 $1$ 件。

总利润为：$2\times (3-2)+2\times(3-1)+1\times (8-4)=10$。

【样例下载】

样例下载

【数据规模与约定】

对于$100\%$的数据，$n\leq 500, m\leq 2000,k\leq 10^4, 1\leq x<y\leq n, 1\leq a_i< b_i\leq 100$，输入保证捆绑关系$(x,y)$不会出现重复。

特殊性质$A$：所有的商品都直接或间接与其他商品捆绑。

【来源】

2024年校际联合邀请赛 入门组-第3场 Task3