Bessie vuelve de un largo viaje extranjero y Farmer John quiere una bonita pancarta «Bienvenida a casa» en su pasto. Cuelga entre dos postes con alambre de longitud $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
El pasto mide $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), con poste en cada coordenada entera. Elige exactamente dos de los $(W + 1) * (H + 1)$ puntos para sujetar los extremos del alambre de la pancarta.
Para no interferir, no debe haber poste justo bajo el alambre tenso entre los dos elegidos.
Calcula las maneras. Son muchas y quizá no baste un entero de 32 bits.
Ejemplo $W = 2$, $H = 1$:
* * *
* * *Tamaño $2..3$. Hay $(2+1) * (1+1) = 6$ puntos y $\binom{6}{2} = (6*5)/(2*1) = 15$ parejas posibles:
| $(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)$ |
Solo cuatro tienen longitud $2..3$:
| Longitud | Longitud | ||
|---|---|---|---|
| $(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)$ y $(0,1)-(2,1)$ tienen poste en la línea entre extremos y no sirven.
Solo dos parejas de 15 sirven.
Entrada
- Línea 1: cuatro enteros $W$, $H$, $L1$, $L2$ separados por espacios.
Salida
- Línea 1: un entero, el número de pancartas posibles.
Ejemplos
Entrada 1
2 1 2 3
Salida 1
2
Autor: Nathan Pinsker, 2010