만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

돌아온 칼슨

시간 제한2초메모리 제한1024 MB

요약
소방관이 창문 사이를 왕복하며 이동할 때, 도둑이 뛰어내리는 구간 안에 소방관이 해당 창문 아래 서 있는 도둑의 수를 셉니다.
난이도

보통10점 중 5점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

한 무리의 사기꾼들이 역대 가장 큰 규모의 강도 사건을 계획했다. 그들은 아주 큰 집에 들어갔고, 문제만 없었다면 확실히 성공했을 것이다. 칼슨이 돌아오겠다고 약속했고, 실제로 돌아왔다! 이제 칼슨이 무서운 사기꾼들은 이 집의 창문으로 뛰어내릴 것이다. 꼬마는 미리 소방관을 불러서 창문에서 뛰어내리는 사기꾼들을 받아 내도록 했다.

이 집에는 창문이 ll개 있다. 소방관은 매 순간 이 창문 중 하나의 아래에서 사기꾼을 받는다. 첫 번째 초에는 1번 창문 아래, 두 번째 초에는 2번 창문 아래에 있으며, 이런 식으로 움직인다. 끝에 도달하면 방향을 바꿔 되돌아온다. 따라서 소방관이 서 있는 창문의 순서는 다음과 같다.

1,2,3,…,l−1,l,l−1,…,2,1,2,…1, 2, 3, \ldots, l - 1, l, l - 1, \ldots, 2, 1, 2, \ldots

꼬마는 사기꾼마다 세 가지를 알고 있다. 첫째, 사기꾼이 뛰어내릴 창문 번호 rir_i. 둘째, 사기꾼이 그 창문으로 달려오는 시각 sis_i. 셋째, 사기꾼이 뛰어내려도 되는 초 단위 시간 tit_i. 이 tit_i초가 지나면 칼슨이 날아와 사기꾼은 반드시 뛰어내려야 한다.

따라서 사기꾼은 구간 [si,si+ti][s_i, s_i + t_i]에 속하는 어느 시각에든 창문 rir_i에서 뛰어내릴 수 있다. 사기꾼은 땅에 순식간에 도달한다고 본다. 이 구간의 시각 중 하나라도 사기꾼의 창문 아래에 소방관이 있으면, 사기꾼은 그 순간 뛰어내려 소방관의 매트에 안전하게 착지한다. 그렇지 않으면 실패한다.

꼬마는 안전하게 착지하는 사기꾼의 수를 세고 싶어 한다. 도와주자.

입력

첫 줄에 두 정수 nn, ll (1≤n,l≤1051 \le n, l \le 10^5)이 주어진다. 각각 사기꾼의 수와 집의 창문 수다.

이어지는 nn개의 줄에는 정수 세 개 rir_i, sis_i, tit_i (1≤ri≤l1 \le r_i \le l, 1≤si,ti≤1091 \le s_i, t_i \le 10^9)가 주어진다. 사기꾼 ii의 창문 번호, 창문에 도착하는 시각, 뛰어내려도 되는 초 수다.

출력

안전하게 착지하는 사기꾼의 수를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    5 4
    2 1 2
    4 1 1
    3 1 2
    4 3 3
    1 1 6
    
    예상 출력
    4