Într-o clădire cu h etaje sunt deţinuţi, la parter, câţiva prizonieri de către T terorişti. Fiecare etaj al clădirii are m x n camere identice. Fiecare cameră are un cod numeric (nu neapărat unic) exprimat printr-un număr din intervalul [0,255]. O trupă antitero formată din K specialişti, trebuie să elibereze prizonierii. Trupa antitero este paraşutată pe clădire şi încearcă să ajungă la parter. Se cunoaşte locul (x, y) unde fiecare membru al trupei a aterizat pe acoperiş. Greutatea fiecărui membru al trupei este exprimată în unităţi din intervalul [1,255]. Un membru al trupei poate trece ″în jos″ printr-o cameră a clădirii doar dacă ″greutatea lui trece prin camera respectivă″, conform următoarei definiţii.

Definiţie: Spunem că ″a trece prin b″ (a>>b) dacă, în reprezentare binară, numărul de cifre 1 a lui a este mai mic sau egal cu numărul de cifre 1 a lui b şi cifrele 1 ale lui a sunt comune cu unele cifre 1 ale lui b.
Exemplu: ″44 trece prin 174″ (44>>174) deoarece
44 = 00101100
174 = 10101110
Pentru detectarea unei camere prin care să poată trece, un membru al trupei de komando se poate, eventual, deplasa cu un ″pas″ în cele 8 direcţii alăturate poziţiei curente în care a ajuns prin aterizare sau trecerea ″în jos″. Prin ″pas″-ul respectiv se ajunge la una din cele 8 camere vecine. Prizonierii pot fi eliberaţi doar dacă la parter ajung minim T membri ai trupei antitero.

Cerinţă

Să se determine numărul de membri ai trupei antitero care pot să ajungă la parter.

Date de intrare

Fişierul de intrare antitero.in are structura următoare: pe prima linie valorile m, n, h, K, T despărţite prin câte un spaţiu, cu semnificaţiile descrise mai sus; următoarele h linii reprezintă codurile celor m x n camere ale unui etaj, despărţite prin câte un spaţiu; ultimele K linii ale fişierului conţin greutatea şi coordonatele x şi y ale poziţiilor de aterizare pe acoperiş ale celor K membri ai trupei antitero, pentru fiecare pe câte o linie, despărţite prin câte un spaţiu:
m n h K T
c111 c112 ... c11n c121 c122 ... c12n ... c1m1 c1m2 ... c1mn
c211 c212 ... c21n c221 c222 ... c22n ... c2m1 c2m2 ... c2mn
...
ch11 ch12 ... ch1n ch21 ch22 ... ch2n ... chm1 chm2 ... chmn
G1 x1 y1
G2 x2 y2
...
GK xK yK

Date de ieşire

Fişierul de ieşire antitero.out va conţine o singură linie pe care va fi scris numărul de membri ai trupei antitero ajunşi la parter.

Restricţii

• 2 ≤ m,n,h ≤ 35
• 1 ≤ xi ≤ m
• 1 ≤ yi ≤ n
• 1 ≤ T, K, Gi ≤ 255
• 0 ≤ cijk ≤ 255
• Toate valorile sunt întregi.

Exemple

antitero.in	antitero.out
5 5 5 3 2 0 0 0 0 0 0 0 33 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 44 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 2 22 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 66 2 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 3 3 3 4 4	2

autor: Prof. Marinel Şerban

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com