M (1<=M<=30,000) 개의 동-서 도로와 N (1<=N<=1,000) 개의 북-남 도로가 있는 도시가 있다. 각 두개의 인접한 도로 사이의 거리는 1m 다. 그리고 이 도시의 각 교차로에는 커피숍이 하나씩 있다.

MxN 개의 커피숍중에 K(1<=K<=1,000) 개의 커피숍에는 무선 인터넷이 있다. 더 정확히 말하자면 i 번째 커피숍은 신호 세기가 Bi(1<=Bi<=1,000)인 무선 인터넷을 거리가 Ri(1<=Ri<=30,000) 미터 안에 들어오는 모든 커피숍에 지원한다.

즉 무선 인터넷을 지원하는 커피숍을 i라고 했을때 커피숍 i 와 커피숍 j의 거리가 Ri 와 같거나 작다면 커피숍 j는 신호 세기가 Bi인 무선 인터넷을 지원 받는다.

커피숍 j의 총 신호 세기는 커피숍 j가 지원받는 모든 무선 인터넷의 신호 세기의 합이다.

N, M, 그리고 K개의 무선 인터넷이 있는 커피숍이 위치한 교차로와 Bi, Ri 가 주어질때 가능한 가장 강한 신호 세기와 그 신호를 받을수 있는 커피숍 개수를 출력하시오.

입력

• 첫번째 줄에는 동-서 도로의 개수인 정수 M이 주어진다.
• 두번째 줄에는 북-남 도로의 개수인 정수 N이 주어진다.
• 세번째 줄에는 무선 인터넷을 지원하는 커피숍 개수인 정수 K가 주어진다.
• 다음 K줄마다 정수 xi(1<=xi<=N), yi(1<=yi<=M), Ri, Bi가 주어진다.

여기서 xi는 i 번째 커피숍이 몇번째 북-남 도로에 위치했는지, yi는 몇번째 동-서 도로에 위치했는지를 알려준다. 맨 아래에 있는 도로나 맨 왼쪽에 있는 도로를 첫번째 도로라고 한다.

출력

• 첫번째 줄에는 가장 강한 신호 세기를,
• 두번째 줄에는 그 신호를 받을수 있는 커피숍 개수를 출력한다.

입출력 예

입력

3
5
3
1 3 2 5
3 1 2 7
5 1 1 5

출력 

12
5

출처: 2009 Canadian Computing Competition Stage 1
번역+추천: likepad