Question
Maximum Sum of K Non-Adjacent elements
You are given an array arr of N non-negative integers and an integer K. Your task is to choose at most K elements from the array such that:
-
No two chosen elements are adjacent in the array.
-
The total sum of the chosen elements is as large as possible.
Return the maximum achievable sum under these conditions.
Input
The first line of input contains two space-separated integers N and K.
The second and final line of input contains N space-separated integers, representing the elements of the array arr.
The second and final line of input contains N space-separated integers, representing the elements of the array arr.
Output
Print an integer representing the maximum total sum that can be achieved.
Example
Input
6 2
1 5 4 3 7 2
Output
12
Explanation
There are 6 elements, and you can select up to 2 non-consecutive elements.
One optimal selection is index 1 (value 5) and index 4 (value 7). These indices are not adjacent, and together they provide the maximum sum of 5 + 7 = 12.
Input
5 0
1 5 4 5 10
Output
0
Explanation
Since no elements can be selected, the total sum remains 0.
6 2
1 5 4 3 7 2
Output
12
Explanation
There are 6 elements, and you can select up to 2 non-consecutive elements.
One optimal selection is index 1 (value 5) and index 4 (value 7). These indices are not adjacent, and together they provide the maximum sum of 5 + 7 = 12.
Input
5 0
1 5 4 5 10
Output
0
Explanation
Since no elements can be selected, the total sum remains 0.