There are several consecutive houses along a street, and each house contains some amount of money. A robber wants to rob some of these houses, but they cannot rob two adjacent houses.

The robber’s capability is defined as the maximum amount of money stolen from any single house among all the houses they choose to rob.

Given an integer array nums, where nums[i] represents the amount of money in the i-th house, and an integer k, representing the minimum number of houses the robber must rob, return the minimum possible capability needed to rob at least k non-adjacent houses.

It is guaranteed that robbing at least k houses is always possible.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $1 \leq$ nums[i] $\leq 10^9$

• $1 \leq$ k $\leq \lfloor($nums.length $+ 1) / 2\rfloor$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.