Taco Selection Challenge

You are given an array of preference scores and an integer k. Your task is to select exactly k items such that no two selected items are adjacent and the sum of their scores is maximized.

Formally, let the array be \(a_0, a_1, \dots, a_{n-1}\). You need to choose a set of indices \(S\) with \(|S| = k\) such that for every index \(i \in S\), neither \(i-1\) nor \(i+1\) is in \(S\). The goal is to maximize the sum:

\[ \sum_{i \in S} a_i \]

If there are multiple optimal selections, any one yielding the maximum sum is acceptable.

inputFormat

The input is read from standard input (stdin) and consists of three parts:

1. The first line contains an integer (n) representing the number of items.
2. The second line contains (n) space-separated integers, where each integer represents the preference score of an item.
3. The third line contains an integer (k) representing the number of items to select.

Note that it is guaranteed that a valid selection exists for the provided input.

outputFormat

Output to standard output (stdout) a single integer — the maximum possible sum of the selected items.## sample

6
1 2 3 1 2 3
2

6