횃불이 키우기

인천대학교의 마스코트, 횃불이는 매우 귀엽습니다. 따라서 용준이는 횃불이 키우기라는 게임을 하기로 했습니다. 횃불이 키우기는 $N$일 동안 횃불이에게 먹이를 줘서 횃불이를 최대한 성장시키는 게임입니다.

횃불이는 정수로 표현되는 크기를 갖고, 초기 크기는 $s$입니다. 횃불이의 크기가 0 이하의 정수가 되면 횃불이는 죽고 게임이 종료됩니다. $i$일차에 먹이를 섭취하면 영양분 $A_i$만큼 크기가 증가합니다.

$i$일차에 용준이는 다음 두 행동 중 하나를 선택할 수 있습니다.

1. $i$일차에 주어진 먹이를 횃불이에게 먹입니다. 이후 횃불이의 크기는 $A_i$만큼 증가합니다.
2. 먹이 섭취를 포기하고 횃불이를 강화합니다. 이후 횃불이의 크기는 2배로 증가합니다.

단, 횃불이는 최대 $k$번 강화할 수 있습니다.

$N$일이 지났을 때, 횃불이의 크기를 가장 크게 만들면 그 크기가 얼마인지 구하는 프로그램을 작성하세요. 횃불이의 크기가 $10^{11}$을 넘게 되면 횃불이는 메가 횃불이로 분류되며, 크기 대신 MEGA를 출력합니다. 어떤 경우에도 횃불이가 $N$일차에 살아남지 못하면 -1을 출력합니다.

첫 번째 줄에 횃불이를 키우는 날 $N$, 횃불이를 강화할 수 있는 횟수 $k$, 횃불이의 최초 크기(0일차) $s$가 공백으로 구분되어 주어집니다. ($1 \leq N \leq 200\,000$, $0 \leq k \leq N$, $1 \leq s \leq 100$)

두 번째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어집니다. $A_i$는 $i$일차에 횃불이가 섭취하는 먹이의 영양분입니다. ($-500 \leq A_i \leq 500$)

$N$일차에 횃불이의 크기를 가장 크게 했을 때 그 크기를 출력합니다. 메가 횃불이가 될 수 있다면 MEGA를, 그렇지 않다면 횃불이의 크기를 나타내는 정수를 출력합니다. 횃불이가 $N$일차에 살아남을 수 없다면 -1을 출력합니다.

Python 사용자는 PyPy로 제출하는 것을 권장합니다.