You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 是一个即将彻底退役的算法竞赛选手了。回首过去的几年，出题一直是小 Y 算法竞赛生涯中充满着回忆的部分。为了保存这段美好的回忆，小 Y 决定从他之前出过的题中选出一些具有代表性的问题，组成一场新的比赛：小 Y 挑战赛！

小 Y 总共出过 $n$ 个问题，每个问题都可以用两个参数来描述：难度 $d_i$ 和有趣程度 $f_i$。

小 Y 将从中挑选一些问题组成小 Y 挑战赛。为了使比赛更加完美，小 Y 希望所选问题能够满足：

• 难度之和 $\in [L，R]$

• 最大化有趣程度之和。

你能帮小 Y 选择组成比赛的题目吗？

由于小 Y 尚未确定最终 $L$ 和 $R$ 的具体情况，他将询问 $q$ 对 $(L_i，R_i)$ 的答案，请计算每个查询的最佳结果。

输入格式

从 choose.in 文件读入数据。

第一行包含两个整数 $n，q$，表示题目数和查询数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $d_i，f_i$ ，表示第 $i$ 道题的难度和有趣程度。

接下来 $q$ 行，每行包含两个整数 $L_i，R_i$，表示一个查询。

输出格式

输出到 choose.out 文件。

输出 $q$ 行，第$i$行包含一个整数，表示第 $i$ 个询问对应的可能的最大有趣程度之和。如果无解输出-1。

样例 1

3 3
10 17
20 4
30 7
1 30
41 52
23 25

21
11
-1

对于第一个查询，可以选择第一个问题和第二个问题，它们的难度之和$=10+20=30\in[1,30]$，它们的有趣程度之和$=17+4=21$。

对于第二个查询，可以选择第二个问题和第三个问题。

对于第三个查询，无法选择满足所有要求的问题。

样例 2

点击链接 ex_choose2.in 和 ex_choose2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 保证 $1\le n\le 5000, 1\le q\le 10^5, 1\le d_i\le 10^4, 1\le f_i\le 10^5, 1\le L_i\le R_i\le 10^4$