Bạn là một tên trộm, tuy nhiên bạn là một người cực kì tốt. Bạn thường lấy đi đồ của người giàu và chia cho người nghèo, đó là quy tắc của bạn. Bạn đang sống ở trong một ngôi làng có n người, người thứ i có tổng tài sản là a[i] đồng. Liên tục trong k ngày, bạn lấy đi người của người giàu nhất một đồng để đưa cho người nghèo nhất.
Ví dụ, làng của bạn có 3 người, tài sản lần lượt là [2, 5, 6] thì sau đêm thứ nhất, tài sản của họ sẽ thành [3, 5, 5]. Trong trường hợp tất cả mọi người có số tài sản bằng nhau, bạn sẽ không lấy tiền của ai cả.
Bạn muốn biết sau k ngày ăn trộm liên tục, chênh lệch giữa người giàu nhất và nghèo nhất là bao nhiêu.
Chú ý nếu có nhiều người cùng giàu hoặc cùng nghèo, bạn có thể chọn ngẫu nhiên và kết quả bài toán không ảnh hưởng.
Input:
Dòng đầu gồm 2 số n và k.
Dòng sau gồm n số, a[i] là tài sản của người thứ i. ( a[i] <= 109)
Output:
Kết quả bài toán.
SUB1: n <= 105, k <= 105
SUB2: n <= 105, k <= 109
| Inp | Out |
|
3 1 2 5 6 |
2 |