Eoi Practice HomeWork

Home work statment

.......................................

B. Candies

Mr. X loves kids and enjoy playing with them. He is used to go weekly to an orphans house and stay the whole day there. Today he brought with him N boxes of candies for N kids. He was very happy for getting this candy treasure for them as this will make their day! But when he reached the house and waiting for them he got shocked that not all boxes are having the same number of candies, and this will make the kids jealous, and maybe fight with each other. So, now he wants to remove candies from the boxes so that to make them equal, the problem is that he only have time to remove total of K candies from the boxes. You are his programmer friend, so he called you to help him. Given the number of candies in each box, help Mr. X to remove at most K candies from the boxes so that after removing them the gap between the maximum box having candies and the minimum box is minimized or become zero if he is lucky and have enough time to make them all equal. Input The first line will contain two spaceseparated integers N, the number of the candy boxes and K, the maximum total number of candies Mr. X can remove from the boxes. On the second line, N spaceseparated positive integers, ai the number of candies in box i. Output Output on the first line and only two spaceseparated integers, the number of candies in the smallest box and the number of candies in the biggest box after Mr. X have removed at most K candies from the boxes.

Subtasks

SUBTASK 1 (40 Points) ● It is guaranteed that, K, the number of candies which Mr. X can remove before the kids come, will be enough for him to make all the boxes equal. i.e. G will always be zero.

● (1 <= N <= 1,000)

● (1,000,000 <= K <= 1,000,000,000)

● (1 <= ai <= 1,000) 1 18 March, 2014 Tunisian Olympiad in Programming Contest Problems

SUBTASK 2 (30 Points)

● (1 <= N <= 1,000)

● (0 <= K <= 1,000,000)

● (1 <= ai <= 1,000,000)

SUBTASK 3 (30 Points)

● (1 <= N <= 100,000)

● (0 <= K <= 1,000,000,000)

● (1 <= ai <= 1,000,000)

Examples

Input Output

1 5 1000000

3 4 7 5 3

3 3

2 4 4

2 3 1 5

1 2

Examples Explanation In the first example, Mr. X have enough time to make all the boxes equal in number of candies, so he will remove 1 candy from the second box, 4 candies from the third box, 2 candies from the fourth box and leave the first and last as they are, to be all of them having exactly 3 candies, so the minimum and maximum box having candies will be 3.

In the second example, Mr. X have only time for removing 4 candies, so he will remove 1 from the 2nd and 3 from the last to minimize the gap between the smallest and biggest boxes having candies to be equal to 1. The boxes will have candies {2, 2, 1, 2}, in the same order given in the input, after Mr. X make his moves... with minimum box having 1 candy and maximum box having 2 candies.

---

I need One to help in it and say to me the idea of this H.W and ,How to slove it?