시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB67342346.000%

문제

IGRUS 회장 현정이는 동아리원들이 더욱 열심히 문제를 풀기를 바라는 마음으로 바나나킥을 뿌립니다! IGRUS 회장은 운동장에 바나나킥 X 개를 뿌려 놓았습니다. 처음에 바나나킥은 모두 칸의 중앙에 놓여 있습니다.

운동장은 겉면이 벽으로 둘러싸인 NM 열의 행렬의 형태이며, 각 바나나킥은 항상 왼쪽 혹은 오른쪽으로 초당 한 칸의 속도로 움직입니다.

만약 바나나킥이 운동장의 벽에 부딪힌다면 방향을 반대로 바꾸어 움직입니다. 예를 들어서, 바나나킥이 2 행 1 열의 중앙에 존재하고 왼쪽으로 움직이고 있었다면 1초 후에는 같은 위치에 존재하고 오른쪽으로 움직이는 상태가 됩니다. 바나나킥끼리 서로 충돌하게 된다면 방향을 반대로 바꾸어 움직이게 됩니다. 또한, 바나나킥이 충돌하는 순간에는 한 칸에 두 개의 바나나킥이 존재할 수 있습니다.

운동장의 첫 번째 행의 모든 칸의 중앙에는 각각 IGRUS 회원들이 한 명씩 바나나킥을 먹기 위해 대기하고 있습니다. IGRUS 회원들은 1초에 한 번씩 상, 하, 좌, 우로 인접한 칸의 중앙으로 이동하거나, 아예 이동을 하지 않을 수도 있습니다.

IGRUS 회원들은 한 번 이동할 때마다 1의 에너지를 소모합니다. 이동하지 않는다면 에너지를 소모하지 않습니다. 그리고 이동한 칸에 바나나킥이 존재한다면 바로 바나나킥을 먹어서 없애버립니다. 이동하는 중에는 달리느라 바빠서 바나나킥을 만나도 먹지 못하고 스쳐 지나갑니다.(한 칸에 여러 명이 몰리게 된다면 시작한 열의 번호가 가장 작은 사람이 바나나킥을 먹게 됩니다.)

IGRUS 회원들의 목적은 바나나킥을 최대한 많이 먹는 것이 1순위이며 소모한 에너지를 최소화시키는 것이 2순위입니다.
IGRUS 회원들은 목적을 최대한 잘 수행하기 위해 항상 최선의 방법으로 움직입니다.

운동장의 크기와 바나나킥들의 시작 상태가 주어졌을 때, 목적을 가장 잘 수행한 사람이 먹는 바나나킥의 개수와 소모한 에너지를 계산해 주세요.

입력

첫째 줄에 양의 정수 N, M, X 가 각각 공백을 두고 주어집니다.

그 후 개의 줄에 걸쳐 바나나킥의 정보가 주어진다. 각 줄은 i 번째 바나나킥의 위치를 나타내는 3개의 양의 정수 Ai, Bi, Ci 가 주어집니다.

번째 바나나킥이 Ai Bi 열의 정중앙에 존재한다는 뜻이며, Ci 가 1이면 오른쪽으로 움직인다는 뜻이고 -1이면 왼쪽으로 움직인다는 뜻입니다.

시작하는 순간에 모든 바나나킥은 서로 다른 칸에 존재합니다.

출력

목적을 제일 성공적으로 수행한 사람이 먹은 바나나킥의 개수와 소모한 에너지의 양을 공백으로 구분하여 출력합니다.

제한

  • 2 ≤ N ≤ 1,000,000,000
  • 1 ≤ M ≤ 1,000,000,000
  • 1 ≤ X ≤ 200,000
  • 2 ≤ Ai ≤ N
  • 1 ≤ Bi ≤ M

예제 입력 1

3 5 3
3 1 1
3 2 -1
2 4 -1

예제 출력 1

2 2

예제 입력 2

34 8 6
14 8 1
2 6 -1
4 7 -1
5 3 1
3 4 1
7 1 -1

예제 출력 2

2 6

예제 입력 3

34 8 17
14 8 1
2 6 -1
4 7 -1
5 3 1
3 4 1
7 1 -1
14 4 1
3 6 1
5 7 1
5 2 1
26 5 -1
20 4 -1
22 1 -1
22 3 1
29 4 1
11 5 1
25 6 -1

예제 출력 3

4 6

예제 입력 4

22 6 19
16 4 -1
5 2 1
8 4 -1
5 3 1
11 6 -1
2 3 1
19 5 1
22 5 -1
13 6 -1
6 6 1
18 6 1
17 5 1
19 6 1
8 6 -1
3 4 1
8 3 1
15 6 -1
8 2 1
16 1 1

예제 출력 4

6 16

힌트

이해를 돕기 위한 설명

(x, y)는 열을 의미합니다. 


0초 - (2,1)에 바나나킥 하나 (2,2)에 바나나킥이 하나 있는 상황입니다. 둘 다 왼쪽으로 움직이는 상황입니다.


0.5초 - (2,1)에 있던 바나나가 벽에 부딪혀서 방향을 바꿉니다.


1초 - 두 바나나가 (2,1)에서 충돌합니다. 만약 이때 (2,1)에 도착하는 회원이 있다면 두 바나나킥을 모두 먹습니다.

 


2초 - (2,1)과 (2,2)에 있는 바나나킥 모두 오른쪽을 향하게 됩니다.

 

출처

University > 인하대학교 > 2020 IGRUS Newbie Programming Contest K번