题目描述

在一条笔直的公路上，有 $n$ 个物资仓库，第 $i$ 个仓库位于坐标 $p_i$，库存量为 $c_i$ 吨。所有仓库位置两两不同。

一天，公路上某一段发生了塌方，区间 [L, R] 的道路被封闭，车辆无法通过。因此，所有物资只能从塌方区间的 同一侧 运输（要么全部从左侧运过来，要么全部从右侧运过来）。

集中物资到位置 x 的总运输成本为：

• 若 x ≤ L（左侧集中），只能运输塌方区间左侧的仓库，因此总运输成本为：

• 若 x ≥ R（右侧集中），只能运输塌方区间右侧的仓库，因此总运输成本为：

• 若 L < x < R，则集中点位于塌方区间内，无法集中物资，输出 -1。

现在有 $q$ 次独立询问，每次给定塌方区间 [L, R] 和一个候选集中点 $x$，求在道路封闭情况下的最小运输成本。如果无法集中物资，输出 -1。

输入格式

第一行两个整数 $n$, $q$。 接下来 $n$ 行，每行两个整数 $c_i, p_i$。 接下来 $q$ 行，每行三个整数 $L, R, x$。

输出格式

对每个询问输出一行一个整数，表示最小运输成本，或 -1。

样例

3 2
2 1
1 5
3 8
3 6 2
2 4 7

2
5

提示

数据范围

• $1 ≤ n, q ≤ 2×10^5$
• $1 ≤ c_i ≤ 10^4$
• $-10^9 ≤ p_i, L, R, x ≤ 10^9$