Robot - MP


Submit solution

Points: 5
Time limit: 0.15s
Memory limit: 8M

Problem type

Fie un teren format din N*M pătrate, se află un robot în poziţia (1,1).
Robotul se poate deplasa pe verticală sau orizontală ( paralel cu axa Oy sau paralel cu axa Ox). La fiecare deplasare, pe orizontală sau verticală, robotul consumă 1 secundă. K bile vor fi plasate pe teren. Pentru fiecare bilă se cunosc următoarele informaţii: timpul plasării pe teren ti, poziţia unde este plasată ( xi, yi) şi valoarea bilei vi. Dacă in momentul plasării bilei pe teren, distanţa manhattan dintre poziţia robotului şi poziţia bilei este mai mică sau egală cu P atunci robotul va putea prinde bila.

Cerință

Determinaţi suma maxima a valorilor bilelor prinse de robot.

Input

Pe prima linie a ecranului se vor gasi numerele naturale N, M, P, K, cu semnificaţia din enunţ. De pe următoarele K linii se vor citi, pentru fiecare bilă, câte patru numere naturale: timpul plasării pe teren ti, poziţia unde este plasată ( xi, yi) şi valoarea vi.

Output

Ecranul va conţine un număr natural, reprezentând suma maximă a valorilor bilelor prinse de robot.

Restricții și precizări

  • robotul va fi plasat în poziţia (1,1) la timpul 0
  • 0 < N , M \le 30
  • 0 \le P \le N + M
  • 0 < K \le 30
  • 0 \le vi \le 1000000
  • 1 \le xi \le N
  • 1 \le yi \le M
  • ti \le 1000000000
  • distanţa manhattan dintre două poziţii în plan ( xi, yi) şi ( xj, yj) este egală cu | xi - xj | + | yi - yj |

Sample Input

2 2 0 2
1 2 1 1
2 1 1 2

Sample Output

3

Comments

There are no comments at the moment.