문제
문홍윤 코치는 점프의 달인이다.
오늘은 문홍윤 코치가 여러분의 앞에서 점프 묘기를 보여줄 것이다.
문홍윤 코치는 운동장에 준비된
문홍윤 코치는
공중제비는 정확히 자연수 바퀴만 돈다. (잘 생각해보자. 1.5바퀴를 돌고 착지하면 머리부터 떨어진다.)
이 점프 시의 착지 위치는 공중제비 한 바퀴당
다시 말해
홍윤 코치는 여러 번 점프를 이어 할 것이고 원한다면 아무 칸에서나 점프를 멈출 수 있다.
이렇게 몇 번 점프를 하고 멈추기까지를 하나의 묘기라고 부른다.
홍윤 코치가 기분이 안 좋으면 한 번의 점프도 보여주지 않고 끝낼 수도 있으며 이것도 묘기다.
두 묘기가 착지하는 칸의 집합이 같을 때 그 둘을 같은 묘기라고 부른다.
홍윤 코치는 몇 개의 서로 다른 묘기를 할 수 있을까?
너무 많으니
입력
첫 줄에
이후
<제한>
1\le N \le 10^5 0\le d_i \le 10^9 0\le x_i \le 10^9
출력
문홍윤 코치가 보여줄 수 있는 서로 다른 묘기의 가지수를
부분문제
번호 | 점수 | 조건 |
---|---|---|
#1 | 8점 | |
#2 | 13점 | |
#3 | 16점 | 모든 |
#4 | 34점 | 모든 |
#5 | 29점 | 추가적인 조건이 없다. |
예제1
5
1 3
2 1
1 3
0 10
3 5
7