rlatjwls3333   7달 전

문제

닥터 옥타비아 스프루트의 파란 머리를 멈추게 하는 일은 쉽지 않았다. 하지만 용감함, 대담함, 그리고 의사의 초능력 덕분에 펭귄들은 결국 해내는 데 성공했다. 이제 그들은 모두 함께 <<북쪽 바람>> 증기선에 앉아, 방금 있었던 전투를 이야기하고 있다.

슈리에 따르면, 이 펭귄 무리들은 무작위로 움직인 것이 아니라 일정한 알고리즘에 따라 움직였다. 모든 펭귄들은 n개의 그룹으로 나뉘어 있었고, i번째 그룹에는 c_i마리의 펭귄이 있었다. 모든 펭귄이 수직선 위를 움직인다고 생각하자. 그러면 i번째 그룹은 점 a_i에서 공격을 시작해서, 한 번 움직일 때마다 b_i만큼 전진했다. 즉, i번째 그룹의 경로는 다음과 같은 점들의 열로 나타낼 수 있다:

a_i, a_i + b_i, a_i + 2b_i, …, a_i + jb_i, …

그리고 이 수열의 모든 점을 c_i마리의 펭귄이 전부 지나간다. 다시 말해, 이 수열은 무한히 이어진다.

황제의 비밀 요원들은 또 하나의 흥미로운 관찰을 했고, 모두에게 다음 문제를 고민해 보자고 제안했다. 주어진 수 k에 대해, 공격 전체 과정에서 좌표가 k인 점을 지나간 펭귄이 총 몇 마리인지 구하는 것이다.

하지만 <<북쪽 바람>>의 펭귄들은 이 문제를 오랫동안 고민했음에도 답을 찾지 못했다. 도와주자!

입력

첫째 줄에 두 정수 n, k가 주어진다.
(1 ≤ n ≤ 100000, 1 ≤ k ≤ 10^9)

여기서 n은 펭귄 그룹의 수이고, k는 그 점을 지난 펭귄 수를 구해야 하는 좌표이다.

다음 n개의 줄 중 i번째 줄에는 세 정수 a_i, b_i, c_i가 주어진다.
(1 ≤ a_i, b_i, c_i ≤ 10^9)

여기서 a_i는 i번째 그룹의 시작 위치, b_i는 한 번의 점프 길이, c_i는 그 그룹에 속한 펭귄의 수이다.

출력

좌표가 k인 점을 지나간 펭귄의 총 수를 출력한다.

예제 입력 1

2 3
1 1 2
1 2 3

예제 출력 1

5

예제 입력 2

2 4
1 1 2
1 2 3

예제 출력 2

2

노트

첫 번째 예제에서 첫 번째 그룹은 {1, 2, 3, 4, ...}를 지나고, 두 번째 그룹은 {1, 3, 5, 7, ...}를 지난다.

첫 번째 그룹에는 펭귄이 2마리, 두 번째 그룹에는 3마리 있으므로, 좌표 3을 지나는 펭귄 수는 총 5마리이다.

두 번째 예제에서는 두 그룹 모두 같은 점들을 지나며, 좌표 4를 지나는 펭귄 수는 총 2마리이다.

댓글을 작성하려면 로그인해야 합니다.