Bessie가 긴 해외여행에서 돌아와 Farmer John이 목초지에 예쁜 «집에 돌아온 걸 환영해» 현수막을 세웁니다. 두 기둥 사이 선에 걸며 길이는 $L1$..$L2$($1 \le L1 \le L2; L1 \le L2 \le 1,500$)입니다.
목초지는 $W \times H$($1 \le W \le 1,000; 1 \le H \le 1,000$)이며 모든 정수 좌표에 기둥이 있습니다. $(W + 1) * (H + 1)$개 중 정확히 둘을 골라 선 양끝을 받칩니다.
방해받지 않도록 선택 기둥 사이 팽팽한 선 바로 아래에는 기둥이 없어야 합니다.
거는 방법 수를 구하세요. 수가 커 32비트 정수로 부족할 수 있습니다.
예제는 $W = 2$, $H = 1$입니다.
* * *
* * *크기는 $2..3$이며 $(2+1) * (1+1) = 6$개 점과 $\binom{6}{2} = (6*5)/(2*1) = 15$개 후보 쌍입니다.
| $(0,0)-(0,1)$ | $(0,0)-(2,1)$ | $(0,1)-(2,1)$ | $(1,1)-(2,0)$ |
| $(0,0)-(1,0)$ | $(0,1)-(1,0)$ | $(1,0)-(1,1)$ | $(1,1)-(2,1)$ |
| $(0,0)-(1,1)$ | $(0,1)-(1,1)$ | $(1,0)-(2,0)$ | $(2,0)-(2,1)$ |
| $(0,0)-(2,0)$ | $(0,1)-(2,0)$ | $(1,0)-(2,1)$ |
길이 $2..3$인 것은 넷뿐입니다.
| 길이 | 길이 | ||
|---|---|---|---|
| $(0,0)-(2,0)$ | $2.00$ | $(0,1)-(2,0)$ | $2.24$ |
| $(0,0)-(2,1)$ | $2.24$ | $(0,1)-(2,1)$ | $2.00$ |
$(0,0)-(2,0)$와 $(0,1)-(2,1)$은 끝점 사이 선에 기둥이 있어 부적합합니다.
15개 중 둘만 가능합니다.
입력
- 1번 줄: 공백으로 구분된 정수 $W$, $H$, $L1$, $L2$.
출력
- 1번 줄: 가능한 현수막 수인 정수 하나.
예제
입력 1
2 1 2 3
출력 1
2
문제 작성: Nathan Pinsker, 2010