TACHANKA - Save Lord Tachanka

Our friend Lord Tachanka is on an important mission. He has to reach basecamp quickly. But the evil enemies have stolen many LMG's and have placed them along the way. You'll have to help him out!

Lord Tachanka is initially at the top left corner (1,1) of a rectangular N × M grid. He needs to reach the bottom right corner (N,M). He can only move down or right. He moves at the speed of 1 cell per second. He has to move every second—that is, he cannot stop and wait at any cell.

There are K special cells that contain the LMG planted by the enemies. Each LMG has a starting time t and a frequency f. It first fires at time t seconds, followed by another round at time t+f seconds, then at time t+2f seconds …. When a LMG fires, it simultaneously emits four bullets, one in each of the four directions: up, down, left and right. The pulses travel at 1 cell per second.

Suppose a LMG is located at (x,y) with starting time t and frequency f. At time t seconds, it shoots its first set of bullets. The bullets travelling upwards will be at the cell (x,y-s) at time t+s seconds. At this time, the bullets travelling left will be at cell (x-s,y), the bullets travelling right will be at cell (x+s,y) and the bullets travelling down will be at cell (x,y+s). It will fire next at time t+f seconds. If a bullets crosses an edge of the grid, it disappears. The LMG's are numbered 1 to k, and if two bullets from different LMG's happen to meet, the one coming from the higher numbered LMG survives. At any time, if Lord Tachanka and a bullet are in the same cell, he dies. That is the only way bullet interact with Lord Tachanka. 

But don't be worried, as you can help the Lord. He can contact his basecamp and can report them the exact position of an LMG, and it will be destroyed by air support. But the war is going on, and you as a commander will have to ensure that minimum missiles are wasted.

Given these, you should find the least time (in seconds) in which Lord Tachanka can reach his basecamp safely. Also calculate the minimum LMG's that are needed to be destroyed so that the Lord can reach the basecamp safely.

Constraints

2 <= N, M <= 500

1 <= K <=500

All the frequencies are guaranteed to be integers between 1 and 600, inclusive.

All the starting times are guaranteed to be integers between 0 and 600, inclusive

All the coordinates of the LMGs are guaranteed to be valid cells in the N×M grid.

No two LMGs will be on the same cell.

Input

Line 1: Three space separated integers N, M and K, describing the number of rows and columns in the grid and the number of LMG's, respectively.

Lines 2 to K+1: These lines describe the K LMGs. Each line has four space separated integers. 

The first two integers on the line denote the row and column where the LMG is located, 

the third integer is its starting time, and the fourth integer is its frequency.

The LMG's are numbered in the order in which it appears in the input, i.e. from 1 to k

Output

You need to output two integers, the minimum amount of time required for the Lord to reach the basecamp, and the minimum LMG's needed to be destroyed.

Example

Input:
4 4 1
3 2 1 3

Output:
6 0

Added by:Rahul
Date:2017-06-30
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2022-12-05 15:28:07
Since Lord Tachanka is keeping moving down or right, is the amount time for he to reach the basecamp constant?
2018-05-25 15:08:43
Can Lord Tachanka enter a cell that contains an LMG?
What happens when a bullet enters a cell containing an LMG?
Can any LMG be destroyed at any time by a missile?
If an LMG is destroyed at time t=0 and it should fire at time t=0 will it fire?
What if Lord Tachanka reaches base camp at the same time as a bullet?
This is an interesting problem but the conditions are not clear enough.

Last edit: 2018-05-25 21:07:59
2018-03-23 10:07:17
Wrong answer in 15th case. Can you please check my submission?

Last edit: 2018-03-23 11:43:53
2017-06-30 17:43:19
@Vipul right!
2017-06-30 17:38:47 Vipul Srivastava
we have to minimise the time, and also report the minimum missiles used in the process of minimising the time, right?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.