Bessie volta de longa viagem ao exterior, e Farmer John quer bela faixa «Bem-vinda ao lar» no pasto para sua chegada. Pende entre postes em fio de comprimento $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
O pasto mede $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), com poste em cada coordenada inteira. Escolhe exatamente dois dos $(W + 1) * (H + 1)$ pontos para segurar as pontas do fio da faixa.
Não quer interferência, portanto nenhum poste diretamente sob o fio esticado entre os escolhidos.
Conte as maneiras. São muitas e um inteiro de 32 bits pode não bastar.
Exemplo $W = 2$, $H = 1$:
* * *
* * *Tamanho $2..3$; há $(2+1) * (1+1) = 6$ pontos e $\binom{6}{2} = (6*5)/(2*1) = 15$ pares possíveis:
| $(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)$ |
Só quatro têm comprimento $2..3$:
| Comprimento | Comprimento | ||
|---|---|---|---|
| $(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)$ e $(0,1)-(2,1)$ têm poste na linha entre pontas e não servem.
Só dois pares de 15 servem.
Entrada
- Linha 1: quatro inteiros $W$, $H$, $L1$, $L2$ separados por espaços.
Saída
- Linha 1: um inteiro, a quantidade de faixas possíveis.
Exemplos
Entrada 1
2 1 2 3
Saída 1
2
Autor: Nathan Pinsker, 2010