Un trotuar de lungime $N$ şi lăţime $L$ trebuie pavat cu dale. Dalele sunt de diferite tipuri, dar din fiecare tip avem o cantitate nelimitată. Lungimea dalelor în cazul fiecărui tip este aceeaşi $L$, iar lăţimea poate să fie o valoare dintre $a{~1~}, a{~2~}, a{~3~},... a{~k~}$. Trotuarul are pe suprafaţa lui $M$ zone ocupate, care nu vor fi pavate. Aceste zone au de fiecare dată o formă pătratică de latură $1$ (reprezentând locul unor stâlpi, cutii poştale, canale, etc.). Se cunosc coordonatele acestor $M$ puncte $(x{~1~},y{~1~}), (x{~2~},y{~2~}),... (x{~m~},y{~m~})$. ( $x$ reprezintă coloana, $y$ reprezintă linia punctului).
În exemplele de mai jos vedem trei metode distincte de acoperire a unui trotuar de dimensiuni $6*3$  folosind două tipuri de dale: $1*3$, respectiv $2*3$, având trei zone ocupate pe trotuar, şi anume: $(6,2), (3,1), (6,3)$.

!problema/trotuar/?grader_you_rock.jpg!

!problema/trotuar/?you_rock.jpg!

h2. Cerinţă

h2. Date de intrare

Fişierul $trotuar.in$ conţine pe prima linie $4$ numere naturale $N, L, K,$ şi $M$ separate prin câte un spaţiu, reprezentând lungimea şi lăţimea  trotuarului, respectiv numărul tipurilor de dale şi numărul zonelor ocupate. Pe linia următoare avem cele $K$ lăţimi ale tipurilor de dale: $a{~1~}, a{~2~}, a{~3~},..., a{~k~}$ separate prin câte un spaţiu. Următoarele $M$ linii conţin câte două numere naturale separate prin spaţiu, reprezentând câte o coordonată $(x{~i~},y{~i~})$, pentru fiecare   ale zonelor ocupate.

Fişierul $trotuar.in$ conţine pe prima linie $4$ numere naturale $N, L, K,$ şi $M$ separate prin câte un spaţiu, reprezentând lungimea şi lăţimea  trotuarului, respectiv numărul tipurilor de dale şi numărul zonelor ocupate. Pe linia următoare avem cele $K$ lăţimi ale tipurilor de dale: $a{~1~}, a{~2~}, a{~3~},..., a{~k~}$ separate prin câte un spaţiu. Următoarele $M$ linii conţin câte două numere naturale separate prin spaţiu, reprezentând câte o coordonată $(x{~i~},y{~i~})$, pentru fiecare zona ocupata.

h2. Date de ieşire