Se dă un tablou bidimensional cu N linii și N coloane. Există Q poziții distincte, etichetate cu numere naturale distincte de la 1 la Q, unde în tablou există valoarea 1, la toate celelalte poziții din tablou există valoarea 0. Pentru o poziție oarecare, dintre cele Q date, numim “forța” acelei poziții numărul subtablourilor din tabloul dat care conțin doar o singură valoare 1, cea aflată la acea poziție, restul elementelor din subtablouri fiind egale cu 0.

Cerința

Pentru un șir format din P etichete distincte, dintre cele corespunzătoare celor Q poziții date, se cere să se calculeze suma “forțelor” acestora.

Date de intrare

Pe prima linie a fișierului de intrare f1.in se găsesc numerele naturale N, Q și P, separate prin spațiu. Pe următoarele Q linii se află câte două numere naturale, separate prin spațiu, reprezentând linia și coloana pentru fiecare dintre cele Q poziții unde se află valoarea 1, în ordinea etichetelor lor. Pe următoarele P linii se află câte un număr natural, reprezentând cele P etichete ale pozițiilor pentru care trebuie calculată suma “forțelor”.

Date de ieșire

Fișierul de ieșire f1.out va conține pe prima linie un număr natural reprezentând suma “forțelor” cerută.

Restricții și precizări

• 1 ≤ P ≤ Q ≤ 1.000.
• 1 ≤ N ≤ 5.000.
• Liniile și coloanele tabloului sunt numerotate cu 1, 2, ..., N.
• Pentru 2 puncte, Q = 1
• Pentru 18 puncte, Q ≤ 5
• Pentru 7 puncte, cele Q ≤ 200 poziții unde există valoarea 1 sunt ordonate strict crescător după linii și după coloane
• Pentru 7 puncte, cele Q ≤ 200 poziții unde există valoarea 1 sunt situate pe aceeați linie
• Pentru 7 puncte, N ≤ 10, Q ≤ 200
• Pentru 12 puncte, N ≤ 300, Q ≤ 200
• Pentru 23 puncte, N ≤ 500, Q ≤ 200
• Pentru 8 puncte, Q ≤ 200
• Pentru 16 puncte, nu există alte restricții suplimentare

Exemplul 1:

f1.in

4 1 1
2 2
1

f1.out

36

Explicație

În primul exemplu avem un tablou de dimensiune 4 x 4 și valoarea 1 la poziția (2, 2). Subtablourile care conțin poziția (2, 2) au colțul stânga-sus în zona delimitată de liniile 1 și 2, respectiv coloanele 1 și 2, iar colțul dreapta-jos în zona delimitată de liniile 2 și 4, respectiv coloanele 2 și 4. În total 36 subtablouri.

Exemplul 2:

f1.in

4 3 2
2 2
3 4
4 1
3
1

f1.out

33

Explicație

În al doilea exemplu avem un tablou de dimensiune 4 x 4 și valoarea 1 la pozițiile (2, 2), (3, 4) și (4, 1). Trebuie calculate forțele pozițiilor cu etichetele 3 și 1, deci ale pozițiilor (4, 1) și (2, 2). Subtablourile care conțin doar poziția (4, 1) sunt: cele cu colțul stânga sus în pozițiile (1, 1) sau (2, 1) și colțul dreapta jos în poziția (4, 1); cele cu colțul stânga sus în (3, 1) sau (4, 1) și colțul dreapta jos în (4, 1), (4, 2) sau (4, 3); cea cu colțul stânga sus în (4, 1) și colțul dreapta jos în (4, 4). Astfel forța poziției (4, 1) este 2 + 6 + 1 = 9.
Subtablourile care conțin doar poziția (2, 2) sunt: cele cu colțul stânga sus în pozițiile (1, 1), (1, 2), (2, 1) sau (2, 2) și colțul dreapta jos în pozițiile (2, 2), (2, 3), (2, 4), (3, 2) sau (3, 3); cele cu colțul stânga sus în (1, 2) sau (2, 2) și colțul dreapta jos în (4, 2) sau (4, 3). Forța poziției (2, 2) este egală cu 20 + 4 = 24. Suma celor două forțe este 33.