该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在玩一个很上头的手游，上头的他氪了不少金，但是众所周知，不管你如何氪金，策划小手一划，就能做出一个你打不过去的关卡

徐老师经过不断的积累和氪金，已经拥有了 $n$ 个随从，并且他已经将这 $n$ 个随从依次排好，形成了一个战斗队列，其中第 $i$ 个随从的攻击力是 $x_i$，生命值为 $y_i$

而今天，这个游戏迎来了一个新的模式——挑战塔

这个塔一共有 $m$ 层，每层都有一个 $BOSS$，其中第 $i$ 层的 $BOSS$ 攻击力 $A_i$，生命值为 $B_i$

而挑战塔的战斗是 $1V1$ 赛制，即战斗队列里的随从会根据编号依次跟 $BOSS$ 进行战斗，每回合当前随从和 $BOSS$ 会同时发出攻击，并且同时受到伤害（伤害值等同于对方的攻击力）

若在某回合结束后，当前随从死亡（生命值 $\leq 0$），则由下一名随从继续下一回合的战斗，若在某回合结束后 $BOSS$ 死亡（生命值 $\leq 0$），则玩家获胜，若随从全部死亡还没有击杀 $BOSS$，则玩家失败

现在徐老师想知道，以他现在的战斗队列，击杀每层 $BOSS$ 分别需要派出多少个随从？

P.S. 特别的，若战斗队列的最后一个随从和 $BOSS$ 在同一回合死亡，则判定玩家获胜

输入格式

输入第一行包含两个整数 $n,m$，含义如题

接下来 $n$ 行，每行输入两个整数 $x_i,y_i$ 表示一个随从的攻击力和生命值

接下来 $m$ 行，每行输入两个整数 $A_i,B_i$ 表示这层 $BOSS$ 的攻击力和生命值

特别的，保证 $A_i,B_i$ 分别为两个非降序列（因为层数的提升 $BOSS$ 的能力只会越来越强）

输出格式

输出 $m$ 行，表示挑战第 $i$ 层 $BOSS$ 需要派出的随从数量，如果无法击杀 $BOSS$，则输出 So Sad!

数据范围

对于所有数据满足：$1 \leq n, m, x_i, y_i, A_i \leq 3 * 10^5$, $1 \leq B_i \leq 10^9$

样例输入1

3 5
5 6
6 8
5 8
4 15
5 17
6 19
6 27
6 28

样例输出1

2
2
3
3
So Sad!