Training Site
Sideways banner

Inventory Management

Input: Standard Input (stdin)
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