1219. Maximum Points You Can Obtain from Cards

Given an array cardPoints and an integer k, you must take exactly k cards, each time from either the beginning or the end of the row. Return the maximum total points obtainable. The input is JSON {cardPoints, k}.

Input: JSON {cardPoints, k}.

Output: Integer — the maximum score.

Examples

Input: {"cardPoints":[1,2,3,4,5,6,1],"k":3}
Output: 12
Explanation: Take the last three cards.

Input: {"cardPoints":[2,2,2],"k":2}
Output: 4
Explanation: Any two cards.

Input: {"cardPoints":[9,7,7,9,7,7,9],"k":7}
Output: 55
Explanation: Take every card.

Constraints

• 1<=n<=10^5
• 1<=k<=n

Asked by