<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

163. Wise King
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard input
output: standard output



Once upon a time in a country far away lived a king and he had a big kingdom. He was a very wise king but he had one weakness - he could count only up to three.
Nevertheless, he did not consider this to be a really great drawback, since he had a lot of wizards who could count up to one hundred (and some of them, people said, even up to one thousand). But one day the grief came to the kingdom as the outnumbering barbarians started to approach from all sides. And the king then had to make the most important decision in his life. He had to choose which of his sons to make generals that he would send to the borders of the country to lead the army.
However, the king knew that though some of his sons were smart, just like he was, some of them were quite stupid and could only lower army spirits with their wrong decisions. More precisely, he knew about each of his sons his mental potential - an integer number ranging from minus three to three (remember, that the king could count only up to three). He also knew that the chance of his army defeating barbarians was proportional to the sum of some powers of mental potentials of those of his sons that he would make generals (the power exponent was a positive integer number, the same for all his sons and not exceeding three either). Thus he had to choose such a combination of his sons to lead the army, that this sum would be maximal possible.
However, the king himself could not make all appropriate calculations since, for example, the second power (the square) of a number not exceeding three could be greater than three, and therefore he asked you, his most intelligent wizard, to solve this problem.

Input
The first line of the input file contains the number of the sons of the king (integer number less than or equal to one hundred). The second line contains the positive integer number not exceeding three, the exponent in the formula used to calculate the chance of defeating barbarians. The third line contains the list of mental potentials of king's sons - all integer numbers, not greater than three by their absolute value.

Output
Output the only number - the maximal possible chance of defeating barbarians calculated as the sum described.

Sample test(s)

Input
In the first example below the king should choose his first and third sons to be the generals. In this case the chance to defeat barbarians, which is the sum of cubes of mental potentials of these sons, is eight plus one, that is nine.
In the second example sending his son to lead the army causes the sum to be negative, thus he should not do it and the sum would be zero.

Sample input #1
3
3
2 -1 1

Sample input #2
1
1
-1

Output
Sample output #1
9

Sample output #2
0

Note
Author:	Andrew Stankevich, Andrew Lopatin, Nikolay Durov, Georgy Korneev
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002

<|response|>
1. Abridged problem statement  
Given N (≤100) integer values x_i (–3 ≤ x_i ≤ 3) and an exponent p (1 ≤ p ≤ 3), select any subset of these values (possibly empty) so as to maximize the sum of their p-th powers ∑(x_i^p). You may leave the subset empty (sum = 0). Output the maximum achievable sum.

2. Key observations  
- For each son’s potential x_i, compute a_i = x_i^p.  
- Since |x_i|≤3 and p≤3, a_i is small and easily computed by direct multiplication.  
- If a_i>0, including x_i in the subset strictly increases the total; if a_i≤0, including it cannot increase the sum and may only decrease (or leave) it.  
- Therefore, the optimal strategy is to take exactly those x_i whose p-th power is positive, and skip all others.  
- If all a_i≤0, the best choice is the empty subset, giving sum = 0.

3. Full solution approach  
1. Read N, p, and the list of x_i.  
2. Initialize a running total, ans = 0.  
3. For each x_i:  
   a. Compute its p-th power, a_i = x_i^p.  
      - If p==1: a_i = x_i  
      - If p==2: a_i = x_i * x_i  
      - If p==3: a_i = x_i * x_i * x_i  
   b. If a_i>0, add it to ans; otherwise, ignore it.  
4. After processing all sons, print ans (which will be ≥0).

Time complexity is O(N); memory is O(N) to store inputs (or even O(1) if you process on the fly).

4. C++ implementation with detailed comments  
```cpp
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;           // Number of sons (≤100)

    int p;
    cin >> p;           // Exponent (1 ≤ p ≤ 3)

    long long ans = 0;  // Accumulator for the answer

    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;       // Read the i-th son's mental potential (–3 ≤ x ≤ 3)

        int a;          // Will hold x^p
        if (p == 1) {
            a = x;
        }
        else if (p == 2) {
            a = x * x;
        }
        else {          // p == 3
            a = x * x * x;
        }

        // Only add positive contributions
        if (a > 0) {
            ans += a;
        }
    }

    // If all a_i ≤ 0, ans remains 0 (empty subset)
    cout << ans << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
def main():
    # Read input
    n = int(input().strip())     # Number of sons
    p = int(input().strip())     # Exponent (1, 2, or 3)
    potentials = list(map(int, input().split()))  # List of x_i

    total = 0
    for x in potentials:
        # Compute x**p efficiently for small p
        if p == 1:
            a = x
        elif p == 2:
            a = x * x
        else:  # p == 3
            a = x * x * x

        # Include only if positive
        if a > 0:
            total += a

    # Print the maximum sum (zero if no positive contributions)
    print(total)

if __name__ == "__main__":
    main()
```