실력과 열정

홍익대학교 컴퓨터공학과 승준이는 '알고리즘 분석' 수업을 수강한다.

교수님은 수업에서 실력과 열정을 가장 중요하게 보며, 수업이 진행되는 $N$일 동안 매일 두 값의 곱을 점수에 더한다.

즉, $i$일차의 실력과 열정을 각각 음이 아닌 정수로 수치화한 값을 $A_i$, $B_i$라 하면, 최종 점수는 아래와 같다.

$$A_1B_1+A_2B_2+\cdots+A_NB_N$$

초기 상태에서 승준이의 실력은 $A_0$, 열정은 $B_0$이다.

과도한 공부는 열정의 손실을 일으키고 과도한 열정은 자만을 불러 실력을 줄인다.

승준이는 매일 $i$($i=1,\dots,N$)일차 성적 갱신 전에 두 행동 중 하나를 선택해 현재 상태를 갱신해야 한다.

1. $x$만큼 공부한다 : 열정 수치에서 $K$이상인 정수 $x$를 선택해 실력으로 바꾼다.
   • $A_{i} = A_{i-1} + x,\ B_{i} = B_{i-1} - x \ (K \le x \le B_{i-1})$
2. $x$만큼 쉰다 : 실력 수치에서 $K$이상인 정수 $x$를 선택해 열정으로 바꾼다.
   • $A_{i} = A_{i-1} - x,\ B_{i} = B_{i-1} + x \ (K \le x \le A_{i-1})$

매일 $K$이상의 열정을 실력으로 바꾸거나, $K$이상의 실력을 열정으로 바꿔야한다는 뜻이다.

목표는 승준이가 매일 적당한 행동을 선택해 $N$일 후의 최종 점수를 최대로 만드는 것이다.

$N$일차 수업이 종료된 후에 승준이가 얻을 수 있는 최종 점수를 최대화해 보자.

첫번째 줄에 $N$이 주어진다. ($1 \le N \le 500$)

두번째 줄에 승준이의 초기 실력 수치 $A_0$, 초기 열정 수치 $B_0$, 실력과 열정의 변환 가능한 최소 수치인 $K$가 주어진다.

• $2 \le A_0 + B_0 \le 500$
• $0 \le A_0, B_0 \le 500$
• $1 \le K \le \max(A_0, B_0)$

$N$일차 수업이 종료된 후 승준이가 얻을 수 있는 최종 점수의 최댓값을 출력한다.