Campo da Calcio

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: calcio.c
• Scarica la traccia in C++: calcio.cpp
• Scarica la traccia in Python: calcio.py
• Scarica la traccia in Java: calcio.java
• Scarica la traccia in C#: calcio.cs
• Scarica la traccia in JavaScript: calcio.html

Descrizione del problema

Data la sua passione per il calcio, Valerio ha deciso di creare un campo da calcio nella foresta vicino a casa sua.

La foresta può essere rappresentata come una griglia di $N$ righe (numerate da $0$ a $N-1$) e $M$ colonne (numerate da $0$ a $M-1$). Il campo che Valerio vuole creare ha forma rettangolare e occupa uno spazio di $A$ righe e $B$ colonne. Può scegliere dove posizionarlo, ma deve essere completamente all'interno della foresta.
Purtroppo però nella foresta sono presenti $K$ alberi e Valerio sarà costretto ad abbaterne qualcuno. Aiuta Valerio a calcolare qual è il minimo numero di alberi che deve abbattere per creare il campo da calcio.

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• la prima riga contiene gli interi $N$, $M$, $K$, $A$, $B$;
• le $K$ righe successive contengono le coordinate degli alberi, ciascuna composta da due interi $x$ e $y$.

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è il numero minimo di alberi che Valerio deve abbattere.

Assunzioni

• $T = 16$, nei file di input che scaricherai saranno presenti esattamente $16$ casi di test.
• $2 \le N,M \le 7000$
• $0 \le K \le 30000$
• $1 \le A \le N$ e $1 \le B \le M$
• $0 \le x \le N-1$ e $0 \le y \le M-1$ per $i = 0, \, \dots, \, K - 1$

Note

• Il campo da calcio deve essere interamente compreso nella foresta, cioè non può essere parzialmente fuori dalla foresta.
• Possono esserci più alberi in una stessa cella della griglia.

Esempi di input/output

---

Input:

2

3 4 4 2 3
1 2
1 1
0 1
1 2

5 3 6 2 2
1 1
0 2
3 1
4 1
1 0
2 2

---

Output:

Case #1: 3
Case #2: 1

---

Spiegazione

Nel primo caso d'esempio, Valerio può creare il campo da calcio abbattendo $3$ alberi.

Nel secondo caso d'esempio, Valerio può creare il campo da calcio abbattendo $1$ albero.