Pudge and his Subsequence

Pudge has a lot of love for numbers. One day, he found an array of numbers of size $n$ and decided to give a task to his friend Necro to see if he is able to do it. He asked Necro to create a subsequence of size k. But everything in life comes at a cost. Similarly, every subsequence $s$ has a cost associated with it. Pudge defines the cost as the minimum between: - The maximum of all numbers at