닥터 옥타비아 스프루트의 파란 머리를 멈추게 하는 일은 쉽지 않았다. 하지만 용감함, 대담함, 그리고 의사의 초능력 덕분에 펭귄들은 결국 해내는 데 성공했다. 이제 그들은 모두 함께 <<북쪽 바람>> 증기선에 앉아, 방금 있었던 전투를 이야기하고 있다.
슈리에 따르면, 이 펭귄 무리들은 무작위로 움직인 것이 아니라 일정한 알고리즘에 따라 움직였다. 모든 펭귄들은 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마리이다.
rlatjwls3333 7달 전 3
문제
닥터 옥타비아 스프루트의 파란 머리를 멈추게 하는 일은 쉽지 않았다. 하지만 용감함, 대담함, 그리고 의사의 초능력 덕분에 펭귄들은 결국 해내는 데 성공했다. 이제 그들은 모두 함께 <<북쪽 바람>> 증기선에 앉아, 방금 있었던 전투를 이야기하고 있다.
슈리에 따르면, 이 펭귄 무리들은 무작위로 움직인 것이 아니라 일정한 알고리즘에 따라 움직였다. 모든 펭귄들은
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
예제 출력 1
예제 입력 2
예제 출력 2
노트
첫 번째 예제에서 첫 번째 그룹은
{1, 2, 3, 4, ...}를 지나고, 두 번째 그룹은{1, 3, 5, 7, ...}를 지난다.첫 번째 그룹에는 펭귄이
2마리, 두 번째 그룹에는3마리 있으므로, 좌표3을 지나는 펭귄 수는 총5마리이다.두 번째 예제에서는 두 그룹 모두 같은 점들을 지나며, 좌표
4를 지나는 펭귄 수는 총2마리이다.