It is well known that if a team has strong cohesion, it tends to burst into more powerful energy at critical moments. Thus, while choosing the P.E. club, Zzz wants to participate in a team, which has the top level of cohesion. (If a team has more people who have connection of friendship, this team will have more cohesion)
One day, Zzz needs to choose a team, but he can’t calculate the best answer by himself. So, he tells you the total numbers of people except himself, some connections between them and everyone’s capability value. Please search a team whose condition can satisfy above information. Moreover, as a curious boy, Zzz wants to know a value which is the sum of people’s capability value in intervals L to R including the boundary but the chosen people can’t exceed the number t which Zzz gives you at the beginning. Of course, when you selecting the section, teammates will stand in a row according to the order of the beginning. Now, please draw a conclusion of the maximum value within two seconds to show your wisdom!

The first row of input data includes three integers n, m, t, separated by spaces, and people are numbered 1 to n.
(1 ≤ n ≤ 106  0 ≤ m ≤ 2 × n   1 ≤ t ≤ n)
The second row of input data has n integers w1, w2 … wn (-1000 ≤ w ≤ 1000), which is represented person’s capability value.
For the following m rows, each row has two integers u and v means u and v are good friends(1 ≤ u, v ≤ n).

Output tow integer separated by space.
The first integer represents the minimum number of people in the largest team (Zzz wishes you to choose the team which has the real minimum number when two or more teams’ size is equal). 
The second integer is the largest sum which satisfies the description.

5 4 4
-3 5 1 -2 3
1 2
2 3
3 4
4 5

1 7

逆乾 WIT第二届程序设计竞赛(现场赛)