Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 0.5 seconds
Leon is a preparing to fight an invasion of zombies in a village. However, it is too dangerous to fight zombies unarmed, and Leon has run out of ammunition for his handgun.
Fortunately, the local merchant has N knives on sale, each of which has a particular durability rating. The i-th knife is durable enough to kill d_i zombies.
Leon has enough money to buy all of them, but his briefcase only has enough space to hold K knives.
What is the maximum number of zombies Leon can kill if he packs his briefcase optimally?
The first line contains two space-separated integers, N, the number of knives on sale, and K, the maximum number of knives Leon can hold.
The second line contains N space-separated integers, d_1, d_2, \dots, d_N, the durability ratings of each knife.
You should print a single integer – the maximum number of zombies Leon can kill.
- 1 \le K \le N \le 100\,000
- 1 \le d_i \le 100
- Subtask 1 (30%): K = 1
- Subtask 2 (30%): N \le 1000
- Subtask 3 (40%): No further restrictions apply
Sample Input 1
3 1 4 7 5
Sample Output 1
Sample Input 2
5 3 5 3 9 6 7
Sample Output 2