【问题描述】
梦醒，耳边传来一阵脚步声。
你抬眼，看到一个熟悉的身影——小丁。
不，你又定睛一看，不是小丁，分明是大魔王啊……
“呵呵，你没看错，其实早在那个迷雾森林中，丁国国王的身体就已经被我占据了。身为大魔王，我有很多问题需要处理，所以我需要一个足够聪明的人，帮我处理这一切。显然，你是聪明的，你通过的我的重重考验，我相信，你能够胜任，我的助理。”
……
“你没有权利拒绝。”
就这样，你开始了助理的第一项任务：
大魔王从人界挑选了n种人类（每种人类的数量不限），想要贩卖给魔界。每种人类的价值为wi元，价格为pi元。
一个魔界的购买者会按如下方式购买人类：假设他拥有k元钱，他会不断的选择从他当前有能力支付的人类中选择价值最高的人类购买一个（如果有相同，则优先选择价格低的人类），直到他买不起任何人类。
随着环境、经济政策、市场需求、大魔王以及购买者的心情变化，每种人类的价值和价格可能改变。
现在共有m次修改或询问操作，你需要依次解答。

【输入格式】
第一行两个正整数n,m
接下来n行，每行两个正整数wi,pi,表示第i种人类的价值和价格。
接下来m行，每行为一个修改或询问，格式如下：
1 x w p：表示将第x种人类的价值改为w,价格改为p；
2 k：表示询问k元钱所买下的人类价值总和。

【输出格式】
共若干行，每行依次对应一个询问。

【输入输出样例】
ending.in

3 3
1 1
2 2
3 3
2 10
1 1 6 6
2 10

ending.out
10
9

【数据范围】
对于前20%的数据，n,m,k≤2000
对于另外20%的数据，不存在修改操作
对于100%的数据，n,m≤100000,1≤wi,pi,w,p,k≤109,1≤x≤n