로빈 후드

면접 대비

시간 제한3초메모리 제한256 MB

요약

N명의 재산이 주어질 때, 가장 부유한 사람(동점이면 목록에서 앞선 사람)에게서 100씩 K번 빼앗은 뒤 남은 재산을 구합니다. 빼앗을 수 없으면 impossible을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 힙, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

마을 어른들은 혹독한 겨울을 예상하고 있고, 로빈 후드는 형편이 어려운 사람들을 걱정한다. 늘 그렇듯 그는 부자에게서 훔쳐 왕국의 부를 재분배할 계획이다. 필요한 강도 짓은 $K$ 번이라고 예상한다.

로빈 후드에게는 표적을 정하는 도덕 강령이 있다. 그는 항상 가장 부유한 사람에게서 훔친다. 가장 부유한 사람이 여럿이면 목록에서 맨 앞에 있는 사람을 고른다. 한 번에 100 화폐 단위만 훔치며, 강도 짓 후 잔액이 $0$ 이하로 남는 사람에게서는 절대 훔치지 않는다.

$N$ 명의 부와 강도 짓 횟수 $K$ 가 주어진다. 도덕 강령에 따라 $K$ 번의 강도 짓을 한 뒤 남은 부를 구하라.

입력

첫 줄에 공백으로 구분된 두 정수 $N$ 과 $K$ 가 주어진다. 둘째 줄에는 공백으로 구분된 $N$ 개의 정수 $P_i$ 가 주어지며, 이는 로빈 후드 표적 각각의 부이다.

출력

$K$ 번의 강도 짓을 한 뒤 남은 부를 출력한다. 강도 짓을 그 횟수만큼 할 수 없으면 impossible을 출력한다.

제한

$1 \le N, K \le 10^5$
$1 \le P_i \le 10^9$

예제3

예제 1
입력
```
4 2
100 120 250 13
```
예상 출력
```
100 120 50 13
```
예제 2
입력
```
4 4
100 120 250 13
```
예상 출력
```
impossible
```
예제 3
입력
```
3 4
200 300 300
```
예상 출력
```
100 100 200
```