1443 - 物品统计

有n(1 <= n <= 100000)件物品从1到n依次编号,每件物品i都重量wi和价值vi(0 <= wi, vi <= 100000)。
给出m(1 <= m <= n)个物品编号区间,和一个参考重量x,
请编程统计并输出各个区间中满足重量wi >= x的所有物品的数量总和sum和价值总和tol。

输入

第一行为一个整数n,表示物品的总数量;
接下来的n行,每行两个整数,分别为wi和vi,数字之间用一个空格分隔;
第n+2行为一个整数m,表示物品编号的区间数;
接下来的m行,每行两个整数,分别为每个区间的开始物品编号li和结束物品编号ri(li <= ri);数字之间用一个空格分隔;
最后一行为一个整数x,表示参考重量。

输出

m行,每行两个整数,分别为sum和tol,数字之间用一个空格分隔。

样例

输入

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

输出

3 17
2 14
3 19

来源

数组

题目参数

时间限制 1 秒
内存限制 32 MB
提交次数 0
通过人数 0
统计

上一题 下一题