Maximum Total Score in a Card Game

You are given a card game with the following rules:

• There are \(n\) cards. Each card has a type. There are \(n\) possible types, numbered from \(1\) to \(n\). Additionally, there is a scoring parameter \(k\).
• You draw the \(n\) cards in order. For each card, you have two choices: take it or leave it.
• At any moment, the cards in your hand must be of the same type only.
• After drawing the cards, you may choose to settle (score) your hand. If you have \(x\) cards in your hand when you settle, you obtain a score of \(x^{\frac{k}{2}}\). After settlement, your hand is cleared and the obtained score is added to your total. You may settle your hand at any moment during the drawing process whenever you wish to switch to a new card type later.

The objective is to compute the maximum total score you can achieve by choosing optimally which cards to take and when to settle.

Note that the expression \(x^{\frac{k}{2}}\) should be interpreted in LaTeX format as shown.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The second line contains \(n\) integers, representing the types of the cards in the order they are drawn.

outputFormat

Output a single number: the maximum total score achievable. It is guaranteed that an answer exists which passes all test cases.

sample

5 2
1 2 1 1 2

5