题目背景

WTX 是一位语文老师，最近负责批改同学们期中考的作文，但是有一件事他很烦恼。

题目描述

现在有 $n$ 个学生的作文，编号为 $1\backsim n$ 。每个学生的作文都有自己的字数 $z_i$ 以及优美度 $p_i$ ，WTX老师要给学生们的作文评一个文采值 $Y$ ，文采值 $Y$ 的评定如下：

1. 给定 m 个区间 $[l_i,r_i]$ ， $[l_i,r_i]$ 可能重复；
2. 给定作文最少要求字数 $w$ ；
3. 对于一个区间 $[l_i,r_i]$ 的作文，它的单独文采值 $y_i$ 为：

$y_i=\left(\displaystyle\sum_{j=l_i}^{r_i}\ [z_j\ge w]\ 1\right)\times\left(\displaystyle\sum_{j=l_i}^{r_i}\ [z_j\ge w]\ p_j\right)$

$j$ 为学生的作文编号。

而文采值 $Y$ 为每个单独文采值 $y_i$ 之和。

由于你是班里优秀的学生，WTX老师想问问你这次期中考的每个文采值 $y_i$。

输入格式

第一行包含三个整数 $n,m,w$ ，意义如上。

接下来 $n$ 行，每行两个整数，第 $i+1$ 行表示第 $i$ 个学生作文的字数 $z_i$ 和优美度 $p_i$ 。

接下来 $m$ 行，表示区间，每行两个整数，第 $i+n+1$ 行表示区间 $[l_i ,r_i ]$ ，保证 $1≤l,r≤n$ ，注意，不保证 $l_i \le r_i$。

输出格式

输入共 $m$ 行，每行一个整数，表示每个文采值 $y_i$

样例

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

6
6
16
0

提示