물풍선 테러리스트

NYPC 2020 · 예선

물풍선 테러리스트 로두마니는 물풍선 아티스트 마리드의 그림을 망치기 위해 마리드가 설치해놓은 물풍선을 모두 터트리려고 한다. (아쉽게도 물풍선이 모두 터져야 마리드가 원하는 그림이 완성된다는 사실은 모르는 듯하다.)

NN 개의 물풍선이 무한한 2차원 격자판에 설치되어 있다. 이때 ii 번째 (1iN)(1 \le i \le N) 물풍선은 (xi,yi)(x_i, y_i) 위치에 세기 pip_i로 설치되어 있다. 설치된 물풍선의 위치는 모두 다르다.

물풍선이 터지면 물풍선의 세기만큼 가로세로 방향으로 물줄기를 발사한다. ii 번째 물풍선이 터지면, 가로 방향으로는 (xipi,yi)(x_i - p_i, y_i), (xipi+1,yi)(x_i - p_i + 1, y_i), ..., (xi+pi1,yi)(x_i + p_i - 1, y_i), (xi+pi,yi)(x_i + p_i, y_i)에 해당하는 부분에 물줄기가 닿게 되며, 세로 방향으로는 (xi,yipi)(x_i, y_i - p_i), (xi,yipi+1)(x_i, y_i - p_i + 1), ..., (xi,yi+pi1)(x_i, y_i + p_i - 1), (xi,yi+pi)(x_i, y_i + p_i)에 해당하는 부분에 물줄기가 닿게 된다. (xi,yi)(x_i, y_i)에도 물줄기가 닿게 된다. 만약 이 물줄기가 다른 물풍선에 닿는다면 해당 물풍선 또한 터지게 되며, 이로 인해 연쇄적인 물풍선 폭발이 일어날 수도 있다. 단, 각각의 물줄기가 닿는 범위는 독립적이며 그 과정에서 터지는 다른 물폭탄의 영향을 받지 않는다.

<그림 1> 세기 3의 물풍선이 터질 때 물줄기 범위 예시
<그림 1> 세기 3의 물풍선이 터질 때 물줄기 범위 예시

로두마니는 다음과 같은 과정을 통해 이 물풍선들을 전부 터트리려 한다:

  1. 물풍선이 남아있는지 확인한다. 남아있는 물풍선이 없다면 과정을 종료한다.
  2. 남아있는 물풍선 중 하나를 골라 바늘로 터트린다.
  3. 물풍선 폭발이 모두 종료되길 기다린 후, 1단계로 돌아간다.

로두마니에게 필요한 바늘 개수는 위 과정 중 2단계가 반복된 횟수와 같다. 다만 로두마니는 아직 본인의 바늘을 사용할지 남의 바늘을 훔쳐서 사용할지 결정하지 않았기 때문에 필요한 바늘 개수의 최솟값과 최댓값 중 무엇을 구할지 고민하고 있다.

설치되어 있는 NN 개의 물풍선 정보가 주어지면, 물풍선을 모두 터트리기 위해 필요한 바늘의 최솟값 또는 최댓값을 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에 설치된 물풍선의 개수를 나타내는 정수 NN이 주어진다. (1N500000)(1 \le N \le 500\,000)

둘째 줄에는 문자열 SS가 주어진다. SSmin 또는 max 이다. SSmin이면 필요한 바늘 개수의 최솟값을, max이면 필요한 바늘 개수의 최댓값을 구해야 한다는 의미이다.

다음 NN 개의 줄에 걸쳐 물풍선의 위치와 세기를 나타내는 정수 xi,yi,pix_i, y_i, p_i가 공백을 사이에 두고 주어진다. (1xi,yi,pi1000000000)(1 \le x_i,y_i,p_i \le 1\,000\,000\,000)

모든 물풍선은 서로 다른 위치에 설치되어 있다.

출력 형식

SSmin인 경우에는 필요한 바늘 개수의 최솟값, max이면 필요한 바늘 개수의 최댓값을 첫 줄에 출력한다.

예제 1

입력

5 min 1 1 10 3 1 1 5 1 3 1 5 3 1 8 3

출력

1

예제 2

입력

5 max 1 1 10 3 1 1 5 1 3 1 5 3 1 8 3

출력

4

예제 설명

입력 예제 1의 경우 (1,1)(1, 1) 위치의 물풍선을 바늘로 터트리면 모든 물풍선이 연쇄적인 폭발로 터지게 된다. 이때 (1,1)(1, 1) 위치의 물풍선의 물줄기가 (3,1)(3, 1) 위치의 물풍선에 가로막히지 않고 (5,1)(5, 1) 위치의 물풍선에게도 닿게 됨을 유의하라.

입력 예제 2의 경우 (1,5)(1, 5), (1,8)(1, 8) 위치의 물풍선 중 하나를 바늘로 터트리면 나머지 하나도 터지게 되므로, 필요한 바늘 개수가 5인 방법은 존재하지 않는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 21

N2500N \le 2\,500

종류 2: 35

SS는 항상 min

종류 3: 35

SS는 항상 max

종류 4: 9

추가적인 제한 조건이 없음.

해설