아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Robin Hood

면접 대비

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

요약
남은 돈이 100보다 많은 사람 중 가장 부유한 사람에게서 100씩 K번 훔칠 때, 마지막 재산을 출력하고 불가능하면 impossible을 출력한다.
난이도

보통10점 중 5점

유형
힙, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

Elders of the village foresee a harsh winter and Robin Hood is worried about the wellbeing of those less well off. As usual, he will be doing a bit of wealth redistribution in the kingdom, that is, he plans to steal from the rich. He estimates that KK heists will be required. However, Robin Hood has a moral codex that determines who the best target is. He always steals from the richest person – if there are several, he will pick the first one on the list. He only steals 100100 monetary units at the time and never steals from anybody who would be left with 00 (or less) money after the heist.

You are provided with the information about the wealth of NN men and the number of heists, denoted as KK. Compute the amount of wealth left after KK performed heists according to the described moral codex.

입력

The first line contains two space-separated integers, NN and KK. The second line contains NN space-separated integers P_iP\_i, the wealth of all Robin Hood’s targets.

출력

Print the amount of wealth after the KK thefts, or print impossible if Robin Hood cannot perform that many thefts.

제한

  • 1≤N,K≤1051 ≤ N, K ≤ 10^5
  • 1≤P_i≤1091 ≤ P\_i ≤ 10^9

예제3

  1. 예제 1

    입력
    4 2
    100 120 250 13
    
    예상 출력
    100 120 50 13
    
  2. 예제 2

    입력
    4 4
    100 120 250 13
    
    예상 출력
    impossible
    
  3. 예제 3

    입력
    3 4
    200 300 300
    
    예상 출력
    100 100 200