题目描述

有 $n$ 个敌人，你有两种攻击他们的方式：

1. 花费 $1$ 的代价，选择一个敌人，对其进行一次普通攻击。

2. 使用一颗炮弹，对所有敌人造成一次爆炸。

对于第二种攻击方式，有 $m$ 颗炮弹可供使用，使用第 $i$ 颗炮弹需要花费 $c_i$ 的代价，并造成一次威力为 $d_i$ 的爆炸。每颗炮弹只能使用一次。

对于第 $i$ 个敌人，如果其被使用第一种攻击方式攻击了 $a_i$ 次，或者受到了 $k$ 次威力不小于 $b_i$ 的爆炸，就会死亡。

有 $q$ 次修改，每次输入 $op,x,y,z$，如果 $op=1$，表示将 $a_x$ 修改为 $y$，$b_x$ 修改为 $z$。否则 $op=2$，表示将 $c_x$ 修改为 $y$，$d_x$ 修改为 $z$。每次修改后，求出至少需要花费多少代价，才能使所有敌人死亡。修改之间不独立，也即修改的结果会继承。

输入格式

第一行四个正整数 $n,m,q,k$，分别表示敌人个数，炮弹颗数，修改次数，敌人的抗爆属性。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，表示敌人的属性。

接下来 $m$ 行，每行两个整数 $c_i,d_i$，表示炮弹的属性。

接下来 $q$ 行，每行四个整数 $op,x,y,z$，表示一次修改。

输出格式

输出 $q$ 行，每行一个整数，表示每次修改后的答案。

输入样例1

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

输出样例1

10
16
14

样例 $1$ 解释

第一次修改后，直接选择第一颗炮弹，可以将所有敌人炸死，代价为 $10$。

第二次修改后，最优方案是用普通攻击击败所有敌人，代价为 $16$。

第三次修改后，使用第二颗炮弹炸掉第一个敌人，再用普通攻击击败第二个敌人，代价为 $14$。

数据范围

对于所有数据，$1\le n,m,q\le 2.5\times 10^5$，$1\le k\le 10^4$，$qk\le 5\times 10^5$，$1\le op\le 2$，$1\le a_i,b_i,c_i,d_i,y,z\le 10^9$，如果 $op=1$，则 $1\le x\le n$，否则 $1\le x\le m$。