돌아온 칼슨
시간 제한2초메모리 제한1024 MB
소방관이 창문 사이를 왕복하며 이동할 때, 도둑이 뛰어내리는 구간 안에 소방관이 해당 창문 아래 서 있는 도둑의 수를 셉니다.
문제
한 무리의 사기꾼들이 역대 가장 큰 규모의 강도 사건을 계획했다. 그들은 아주 큰 집에 들어갔고, 문제만 없었다면 확실히 성공했을 것이다. 칼슨이 돌아오겠다고 약속했고, 실제로 돌아왔다! 이제 칼슨이 무서운 사기꾼들은 이 집의 창문으로 뛰어내릴 것이다. 꼬마는 미리 소방관을 불러서 창문에서 뛰어내리는 사기꾼들을 받아 내도록 했다.
이 집에는 창문이 개 있다. 소방관은 매 순간 이 창문 중 하나의 아래에서 사기꾼을 받는다. 첫 번째 초에는 1번 창문 아래, 두 번째 초에는 2번 창문 아래에 있으며, 이런 식으로 움직인다. 끝에 도달하면 방향을 바꿔 되돌아온다. 따라서 소방관이 서 있는 창문의 순서는 다음과 같다.
꼬마는 사기꾼마다 세 가지를 알고 있다. 첫째, 사기꾼이 뛰어내릴 창문 번호 . 둘째, 사기꾼이 그 창문으로 달려오는 시각 . 셋째, 사기꾼이 뛰어내려도 되는 초 단위 시간 . 이 초가 지나면 칼슨이 날아와 사기꾼은 반드시 뛰어내려야 한다.
따라서 사기꾼은 구간 에 속하는 어느 시각에든 창문 에서 뛰어내릴 수 있다. 사기꾼은 땅에 순식간에 도달한다고 본다. 이 구간의 시각 중 하나라도 사기꾼의 창문 아래에 소방관이 있으면, 사기꾼은 그 순간 뛰어내려 소방관의 매트에 안전하게 착지한다. 그렇지 않으면 실패한다.
꼬마는 안전하게 착지하는 사기꾼의 수를 세고 싶어 한다. 도와주자.
입력
첫 줄에 두 정수 , ()이 주어진다. 각각 사기꾼의 수와 집의 창문 수다.
이어지는 개의 줄에는 정수 세 개 , , (, )가 주어진다. 사기꾼 의 창문 번호, 창문에 도착하는 시각, 뛰어내려도 되는 초 수다.
출력
안전하게 착지하는 사기꾼의 수를 한 줄에 출력한다.