닭들의 만남

실행 시간 제한	메모리 제한
1 초	512 MB

📃 해결할 문제

일차원 수직선에 위치 $0$ 과 $L$ $(1 \le L \le 10^9)$ 에 닭장이 있습니다. 또한, 이 숫자선에 $N$ 마리의 닭 $(1 \le N \le 5 \cdot 10^4)$ 이 각각 다른 위치에 있습니다(각 닭과 닭장의 위치를 점으로 생각하세요). 각 닭 $i$ 는 처음에 어떤 위치 $x_i$ 에 있고, 속도가 초당 한 단위인 양의 방향 혹은 음의 방향으로 움직이며, 이는 정수 $d_i$ 로 표현되며, 이 값은 $1$ 또는 $-1$ 입니다. 각 닭은 무게 $w_i$ 를 가지며, 이 범위는 $[1, 10^3]$ 입니다. 모든 닭은 항상 일정한 속도로 움직입니다. 이후로는 다음의 이벤트 중 하나가 발생할 때까지 이동을 계속합니다:

닭 $i$ 가 닭장에 도달하면, 닭 $i$ 는 움직임을 멈춥니다.
닭 $i$ 와 $j$ 가 닭장이 아닌 같은 지점에서 만나면 '만남'이 발생합니다. 이 경우, 닭 $i$ 의 이전 속도는 닭 $j$ 에게, 닭 $j$ 의 이전 속도는 닭 $i$ 에게 할당됩니다. 닭들은 정수가 아닌 다른 지점에서도 만날 수 있습니다.

시간 $T$ 는 움직이지 않는 닭들(닭장에 도달하여 움직이지 않는 경우)의 무게 합계가 모든 닭의 무게 합계의 적어도 절반이 되는 가장 빠른 시점입니다. 시간 범위 $0 \ldots T$ 동안 (시간 $T$ 를 포함하여) 닭 쌍 사이에 발생하는 총 회합 횟수를 결정해 주세요.

💻 입력

첫 번째 줄에는 두 개의 공백으로 구분된 정수 $N$ 과 $L$ 이 주어집니다.

다음 $N$ 개의 각 줄에는 세 개의 공백으로 구분된 정수 $w_i$ , $x_i$ , 그리고 $d_i$ 가 주어집니다. 모든 위치 $x_i$ 는 다르며 $0 \lt x_i \lt L$ 를 충족시킵니다.

🖨️ 출력

답을 포함하는 단일 줄을 출력합니다.

💻 예제 입력 1

🖨️ 예제 출력 1

💡 힌트

이 예제에서, 닭들은 다음과 같은 방식으로 움직입니다:

첫 번째와 두 번째 닭은 0.5 시점에 위치 1.5에서 만납니다. 이때 첫 번째 닭의 속도는 $-1$ 이 되고, 두 번째 닭의 속도는 $1$ 이 됩니다.
두 번째와 세 번째 닭은 1 시점에 위치 2에서 만납니다. 이때 두 번째 닭의 속도는 $-1$ 이 되고, 세 번째 닭의 속도는 $1$ 이 됩니다.
첫 번째 닭은 2 시점에 왼쪽 닭장에 도달합니다.
두 번째 닭은 3 시점에 왼쪽 닭장에 도달합니다.
이 시점에서 무게의 합계가 모든 닭의 무게의 합게의 적어도 절반이 된 닭이 닭장에 도착했기 때문에 과정이 종료됩니다. 세 번째 닭은 4 시점에 오른쪽 닭장에 도착했을 것입니다.

정확히 두 번의 만남이 발생했습니다.

출처: USACO 2019 December Contest, Silver Problem 2. Meetings