왕

먼 옛날 아주 먼 나라에 큰 왕국을 다스리는 왕이 살았다. 왕은 매우 영리했지만 약점이 하나 있었다. 셋까지밖에 세지 못한다는 것이다.

그래도 왕은 이를 큰 흠으로 여기지 않았다. 백까지 세는 마법사가 많았고, 그중에는 천까지 센다는 소문이 도는 마법사도 있었기 때문이다. 그러던 어느 날 수가 훨씬 많은 야만족이 사방에서 밀려오면서 왕국에 시련이 닥쳤다. 왕은 일생에서 가장 중요한 결정을 내려야 했다. 아들 중에서 누구를 장군으로 삼아 국경으로 보내고 군대를 이끌게 할지 골라야 한다.

왕은 아들 중 일부가 자신처럼 영리하다는 것도, 일부는 어리석어서 잘못된 판단으로 군대의 사기만 떨어뜨린다는 것도 알고 있었다. 더 정확히 말하면 왕은 아들마다 지력을 알고 있었다. 지력은 -3 이상 3 이하의 정수이다(왕은 셋까지만 셀 수 있다). 또한 야만족을 물리칠 가능성이 장군으로 삼은 아들의 지력을 거듭제곱한 값의 합에 비례한다는 것도 알고 있었다. 지수는 모든 아들에게 똑같이 적용되는 양의 정수이고, 이 값도 3을 넘지 않는다. 그래서 왕은 이 합이 가장 커지도록 아들을 골라야 한다.

문제는 왕이 직접 계산할 수 없다는 점이다. 예를 들어 3을 넘지 않는 수라도 제곱하면 3보다 커질 수 있다. 그래서 왕은 가장 똑똑한 마법사인 당신에게 이 계산을 맡겼다.

첫째 줄에 왕의 아들 수가 주어진다. 100 이하의 정수이다.

둘째 줄에 야만족을 물리칠 가능성을 계산할 때 쓰는 지수가 주어진다. 3을 넘지 않는 양의 정수이다.

셋째 줄에 아들의 지력이 순서대로 주어진다. 모두 절댓값이 3을 넘지 않는 정수이다.

야만족을 물리칠 가능성의 최댓값을 한 줄에 출력한다. 이 값은 장군으로 삼은 아들의 지력을 지수만큼 거듭제곱한 값을 모두 더한 것이다. 아무도 장군으로 삼지 않아도 되며, 그때 합은 0이다.

첫 번째 예제에서는 첫째 아들과 셋째 아들을 장군으로 삼으면 된다. 이때 야만족을 물리칠 가능성은 두 아들의 지력을 세제곱한 값의 합이므로 8 더하기 1, 즉 9이다.