1928 - 采购礼品

题目描述

王老师来到商店为同学们采购礼品。

这家店有 n 种礼品(编号是 1 \sim n ),每种礼品只有 1 件。老板为了促销,对礼品进行搭配销售,有关联性的礼品必须都要采购(奇怪的规定),比如 1 号礼品和 3 号礼品搭配了,3 号和 8 号礼品搭配了,那么王老师想要买 1 号礼品的话,就需要把 3 号和 8 号礼品都买了。

现给定每种礼品的价钱和价值,请问在有限的钱 w 的情况下,能够买到礼品的最大价值是多少?

输入

第一行输入三个整数,n,m,w,表示有 n 种礼品,m 个搭配和你现有的钱的数目。

第二行至 n+1 行,每行有两个整数,cd,表示第 i 种礼品的价钱和价值。(1≤c,d≤10^5

n+2n+1+m 行 ,每行有两个整数,uv,表示 u 号礼品和 v 号礼品是有关联的,已经形成搭配销售的关系。

数据范围:

1≤n,w≤10^4,0≤m≤5 \times 10^3

输出

一行,表示可以获得的最大价值。

样例

输入

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出

1
来源

背包 并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题