Problem D: Swapping

## Problem D: Swapping

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1738  Solved: 266
[Submit][Status][Web Board]

## Description

There are $$n$$ integers  $$a_1, a_2, …, a_n$$  in an array $$A$$. It's guaranteed that any two digits in $$a_i$$ won't be the same. Suppose you can swap two digits of $$a_i$$ in the array at most $$m$$ times. The cost of each swap is $$k$$. We define $$S = \sum A – x \times k$$, where $$x$$ is the times of swapping applied, $$A$$ is the corresponding integer array after $$x$$ times swapping actions. Please find the maximum value of $$S$$.

## Input

There will be two lines.

The first line will be three integers: $$n, m, k$$.

The second line will be n integers $$a_1, a_2, …, a_n$$.

For all test cases, $$1\leq n\leq 2*10^5, 0\leq m\leq 2*10^5, 0\leq k\leq 10^9, |a_i|\leq 10^9.$$

## Output

There will be only one integer: the maximum value of S

## Sample Input

3 4 20
154 24 15

## Sample Output

556

## HINT

1. Leading zero is permitted after swapping.

2. The sample example only takes 3 swaps.

[Submit][Status]