A relay squad lists n runners in a fixed lineup order, each with an integer skill rating. You must pick exactly k runners to form a team, keeping them in lineup order, so that their ratings are strictly increasing along the team. Among all valid teams, choose the one whose total rating is smallest, and report that total. If no strictly increasing team of exactly k runners exists, report -1.
Line 1: two integers n and k.
Line 2: n space-separated integers, the ratings in lineup order.
A single integer: the minimum total rating of a strictly increasing length-k subsequence, or -1 if impossible.
Example 1
Input
5 3 1 6 2 7 3
Expected
6
Explanation
Strictly increasing teams of 3 include 1,6,7 (=14) and 1,2,3 (=6); the smallest total is 6.
Example 2
Input
4 3 5 4 3 2
Expected
-1
Explanation
Ratings only decrease, so no strictly increasing team of 3 exists; the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →