횃불이 키우기

인천대학교의 마스코트, 횃불이는 매우 귀엽습니다. 따라서 용준이는 횃불이 키우기라는 게임을 하기로 했습니다. 횃불이 키우기는 $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, ..., A_N$이 공백으로 구분되어 주어집니다. $A_i$는 $i$일차에 횃불이가 섭취하는 먹이의 영양분을 나타내는 값입니다. $(-500 \leq\ A_i \leq\ 500)$

$N$일차에 횃불이의 크기를 가장 크게 했을 경우 얼마나 커질 수 있는지 출력해 주세요. 메가 횃불이로 진화할 수 있다면 MEGA를, 그렇지 않다면 횃불이의 크기를 나타내는 정수를 출력해주세요. 만약 횃불이가 $N$일차에 살아남을 수 없다면 $-1$을 출력해 주세요.

Python유저는 PyPy 제출을 권장합니다.