34237번 - 호참전

문제

호랑이와 참새는 매년 친선 경기인 "호참전"을 진행한다! 호참전은 여러 경기로 이루어지며, 매년 전체 경기 수는 달라진다. 각 경기에서 승자는 1ドル$점을, 패자는 0ドル$점을 얻으며, 비기는 경우는 없다.

올해 호참전을 앞두고 $N$마리의 아기 호랑이들이 베팅을 한다. 어떤 아기 호랑이가 $a\ b$ 라고 베팅하면 호참전 진행 중에 정확히 $a:b$가 되는 순간이 존재할 경우 베팅에서 승리하게 된다. 아기 호랑이들은 호랑이가 참새를 상대로 질 것이라고는 생각하지 않기 때문에, 모든 아기 호랑이들의 베팅에 대해 $a \ge b$가 성립한다.

윤헌이는 올해 아기 호랑이들의 베팅이 얼마나 잘 들어맞는지 궁금해졌다. 그래서 지난 $M$년간의 호참전 기록을 살펴보고, 만약 그때도 올해와 똑같이 베팅했다면 몇 마리가 이길 수 있었는지 알아보기로 했다.

$M$년간의 호참전에 대한 정보가 주어진다. 제 $i$회 호참전에 대한 정보는 총 게임 수 $g_i$와, 해당 호참전의 특정 시점의 스코어 $x_i : y_i$로 주어진다. 이 스코어에서 호참전이 재개되었을 때, 몇 마리의 아기 호랑이들이 베팅에서 이기는지를 알아볼 것이다. 윤헌이는 올해 호참전에서 호랑이가 참새를 이길 것이라고 생각하기 때문에, 비슷한 상황을 가정하기 위해 각 호참전에서 $x_i \ge y_i$인 순간들만을 선정하였다.

이때 아기 호랑이들이 올해와 같은 베팅을 했다고 가정할 때, 승리할 수 있는 아기 호랑이의 수를 구하여라. 어떤 베팅 $a:b$가 승리할 가능성이 있다는 것은, 시작 스코어가 $(x, y)$이고 총 경기 수가 $g$일 때

$x \leq a; y \leq b; a+b \leq g$

를 만족함을 의미한다. 위의 세 가지 조건을 모두 만족해야 함에 유의하라.

입력

첫째 줄에 아기 호랑이의 마릿수 $N,ドル 기록을 살펴볼 호참전의 횟수 $M$이 공백으로 구분되어 주어진다. $(1 \leq N \leq 50$; $ 1 \leq M \leq 100,000円)$

다음 $N$개의 줄의 $i$번째 줄에는, $i$번 아기 호랑이의 베팅 $a_i, b_i$가 공백으로 구분되어 주어진다. $(0 \leq b_i \leq a_i \leq 100$; $ a_i + b_i \leq 100)$

다음 $M$개의 줄의 $j$번째 줄에는, 제 $j$회 호참전의 총 경기 수 $g_j,ドル 그리고 해당 호참전의 특정 시점의 스코어 $x_j, y_j$가 공백으로 구분되어 주어진다. $(0 \leq y_j \leq x_j$; $ 0 \leq x_j + y_j \leq g_j \leq 100)$

출력

$i$번째 줄에 제 $i$회 호참전에서 올해와 동일하게 베팅했을 때 베팅에서 승리할 가능성이 있는 아기 호랑이들의 마릿수를 출력한다.

제한

힌트