# [SOLUTION] Judgement Day 2 solution codechef 2021 – Spider AlgoCup Codechef

## Judgement Day 2 solution codechef 2021

You are going to be born as a saint on a planet far from earth. The planet consists of NN islands. Your job is to civilize the islands (not mandatorily all). Each island has its virtue level and you will get a follower from each island you visit.

At each island the virtue level of you and your followers will drop down to the minimum of your current virtue level and virtue level of that island. You and your followers will go to heaven if the sum of the final virtue level of all members in the group (excluding youexcluding you) is greater than KK. Find the maximum value of KK for which your group can go to heaven.

Assume initially you have infinite virtue level and it’s mandatory to visit at least one island. You can start at any island and stop at any island and you will visit all the islands along the path. You can’t visit an island more than once.

NOTE: There won’t be more than one path between two islands and Each island is connected to at max 2 islands.

### Input: Judgement Day 2 solution codechef 2021

• The first line will contain number of islands NN and number of paths MM.
• The next line will contain N spaced integers val[i]val[i], the virtue level of each island.
• The next m lines contains two integers u[i]u[i] and v[i]v[i] which describes a bi-directional path between the islands

### Output: Judgement Day 2 solution codechef 2021

Output the maximum value of KK.

### Constraints: Judgement Day 2 solution codechef 2021

• The islands are numbered from 00 to N1N−1
• 1N1051≤N≤105
• 0v[i],u[i]N10≤v[i],u[i]≤N−1
• 0val[i]1040≤val[i]≤104

### Sample Input 0: Judgement Day 2 solution codechef 2021

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


### Sample Output 0: Judgement Day 2 solution codechef 2021

9


### EXPLANATION 0:

You can start and stop at island 4. If you start from island 3 and stop at island 4, your virtue level will be 2*min(9,4) = 8 (<9).

### Sample Input 1:

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


### Sample Output 1:

9


### EXPLANATION 1:

All the islands are connected in the following order 4<->1<->2<->0 <->5 If you start at island 0 virtue level of the group will be 5. If you move to island 2 from 0, the virtue level of the group will be min(3,5)2=6min(3,5)∗2=6. If you move to island 1 from island 0 (0->2->1), then your virtue level will be min(3,4)3=9min(3,4)∗3=9.