Cloud Purchase Optimization

Tomorrow is Mother's Day, and the kids of the computer club are brainstorming what gift they should give. They heard of a website selling mysterious clouds! In the shop, there are \(n\) clouds labelled \(1, 2, 3, \ldots, n\). Each cloud has a cost and a beauty value. However, the quirky shopkeeper has a special rule: some clouds must be bought in groups. In other words, if you buy a certain cloud, you must also buy all the clouds that are paired with it. With a limited amount of money \(M\), you want to purchase clouds so that the total beauty value is maximized.

You are given:

• An integer \(n\) denoting the number of clouds.
• An integer \(M\) denoting your total available money.
• An integer \(p\) indicating the number of dependency relations.
• An array of \(n\) integers representing the cost of each cloud.
• An array of \(n\) integers representing the beauty value of each cloud.
• \(p\) pairs of integers \((u, v)\), meaning that cloud \(u\) and cloud \(v\) must be bought together (i.e. they belong to the same group).

If any cloud in a group is bought, then the entire group must be purchased together. Determine the maximum total beauty value you can obtain without exceeding your budget \(M\).

Note: Clouds not connected by any dependency can be purchased individually.

inputFormat

The first line contains three space-separated integers \(n, M, p\).

The second line contains \(n\) space-separated integers representing the cost of the clouds.

The third line contains \(n\) space-separated integers representing the beauty value of the clouds.

The next \(p\) lines each contain two space-separated integers \(u\) and \(v\), indicating that clouds \(u\) and \(v\) must be purchased together.

outputFormat

Output a single integer, the maximum total beauty value achievable within the budget \(M\).

sample

3 10 2
3 4 5
5 6 7
1 2
2 3

0