디지털 수수께끼

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n개의 수와 최대 k번의 한 자리 숫자 교체가 주어질 때, 합을 최대로 늘릴 수 있는 증가량을 구합니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

디퍼는 다른 비밀을 쫓던 중 까다로운 수수께끼를 만났다. 칠판에 $n$ 개의 수가 적혀 있다. 임의의 수의 임의의 자릿수를 골라 다른 숫자로 바꿀 수 있다. 단, 이 연산은 최대 $k$ 번까지만 수행할 수 있다. 디퍼는 칠판에 적힌 수의 합을 최대한 크게 만들고 싶어 한다. 이 연산으로 합을 얼마나 늘릴 수 있는지 가장 큰 값을 구하라. 수수께끼 풀이를 도와주자.

입력

첫째 줄에 두 정수 $n$ , $k$ 가 주어진다. $n$ 은 칠판에 적힌 수의 개수, $k$ 는 연산 횟수의 상한이다. ( $1 \le n \le 1000$ , $1 \le k \le 10^4$ ) 둘째 줄에 칠판에 적힌 $n$ 개의 수 $a_i$ 가 주어진다. ( $1 \le a_i \le 10^9$ )

출력

연산을 적용한 뒤의 합과 처음 합의 차이를 한 줄에 출력한다.

힌트

첫 번째 예제에서는 1을 9로 바꾸면 합이 16 늘어난다. 두 번째 예제에서는 85를 95로 바꾸면 합이 10 늘어난다. 세 번째 예제에서는 9999의 어떤 자릿수를 바꿔도 수가 커지지 않으므로 답은 0이다.

예제3

예제 1
입력
```
5 2
1 2 1 3 5
```
예상 출력
```
16
```
예제 2
입력
```
3 1
99 5 85
```
예상 출력
```
10
```
예제 3
입력
```
1 10
9999
```
예상 출력
```
0
```