30407번 - 나비의 간식을 훔쳐먹은 춘배

문제

춘배가 나비의 간식을 뺏어 먹고 도망가자 화난 나비는 냥냥펀치를 날리려 한다.

냥냥펀치 : 문제에서 주어진 $R_i$에서 춘배와 나비 사이의 거리를 뺀 값만큼 춘배의 체력이 깎인다. 데미지가 10ドル$이고 현재 춘배와 나비 사이의 거리가 3ドル$일 경우 7ドル$만큼 체력이 깎인다. 체력이 깎이는 양은 음수가 될 수 없다.

춘배는 도망가다 상자를 발견해서 숨게 되었고 자신이 가진 3ドル$가지 기술로 대응하려 한다.

• 웅크리기: 나비가 공격할 시 데미지가 절반 감소한다. 이는 데미지가 거리만큼 약해진 후 계산된다. 단, 감소 후 데미지의 소수점 아래는 버린다.
• 네발로 걷기: 문제에서 주어진 값 $K$ 만큼 나비와 멀어지는 방향으로 이동할 수 있다.
• 깜짝 놀라게 하기: 나비의 다음 행동을 1ドル$번 무시한다. $i$번째 사용 할 시 $R_{i+1}$를 무시한다. 단 1ドル$번 사용할 수 있고 $N$번째에 사용 시 아무 일도 일어나지 않는다.

한 턴은 춘배의 기술, 냥냥펀치, 데미지 계산의 순서대로 실행된다. 춘배는 턴마다 1ドル$개의 기술만 쓸 수 있다. 나비가 모든 $N$개의 냥냥펀치를 하여 지칠 때까지 춘배가 유지할 수 있는 최대 체력을 알아보자. 어떤 행동을 해도 체력이 0ドル$이하가 된다면 $-1$을 출력한다.

입력

첫 번째 줄에 나비가 지칠 때까지의 냥냥펀치 수 $N$이 정수로 주어진다. $(1 \le N \le 18)$

두 번째 줄에 춘배의 체력 $H,ドル 현재 나비 사이의 거리 $D,ドル 춘배가 네발로 걷기 시 이동하는 거리 $K$가 공백으로 구분되어 주어진다. $(1 \le H \le 1000, 1 \le D \le 10, 1 \le K \le 3)$

세 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 냥냥펀치의 데미지 $R_i$가 주어진다. $(1 \le R_i \le 100)$

출력

춘배가 가질 수 있는 최대 체력을 출력한다. 답이 0ドル$ 이하일 경우 $-1$을 출력한다.

제한

힌트