Redistribució de la riquesa P57539

Statement

Considereu una societat amb $n$ persones, on la persona $i$ -èsima té inicialment $a_i$ euros. Es vol redistribuir part de la riquesa per reduir tant com sigui possible la diferència entre rics i pobres, amb dues limitacions:

No es poden expropiar (per després repartir) més de $k$ euros en total.
Els moviments de diners han de ser enters.

Quina és la mínima diferència que es pot aconseguir entre la persona més rica i la més pobra?

Entrada

L’entrada conté diversos casos, només amb nombres enters. Cada cas té una $n$ entre 1 i $10^5$ , una $k$ entre 0 i $10^{18}$ , i els $a_i$ , tots entre 0 i $10^9$ .

Sortida

Per a cada cas, escriviu la mínima diferència que es pot aconseguir.

Public test cases

Input

5 3  1 2 3 4 5
5 2  1 2 3 4 5
5 1  1 2 3 4 5
3 5  10 10 10
4 6  8 1 1 1
1 6  123
10 2400000000  1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0

Output

Information

Author: Xavier Povill
Language: Catalan
Official solutions: C++ Python
User solutions: C++ Python