CSG-CPC
Online Judge

1227 : 茶和咖啡

         Time Limit: 2 Sec     Memory Limit: 256 Mb     Submitted: 141     Solved: 39     SpecialJudge

Description

中山大学的女孩们喜欢喝茶。但是有一天,她们想要变换口味,所以决定在接下来的 \(n\) 天里尝试一下喝咖啡。

现在,总是为中山大学提供食物和饮料的 Zayin 决定去商店买一些咖啡,她了解到第 \(i\) 天的价格是 \(a_i\)。同时,她有 \(m\) 张优惠券 — 第 \(i\) 张优惠券可以在前 \(r_i\) 天(包括第 \(r_i\) 天)使用,并且可以将当天咖啡的价格减少 \(w_i\)

请注意,每张优惠券只能使用一次,Zayin 可以在一天内使用多张优惠券。使用优惠券后,价格可以是负数。

由于中山大学的女孩们仍然需要喝茶,Zayin 决定选择只在某些天内购买咖啡。现在她想知道,如果她选择恰好 \(k\ (1\le k \le n)\) 天来购买咖啡,她需要花费的最少金额(或者她可以获得的最大金额)是多少呢?

Input

输入的第一行包含一个整数 \(t\ (1\le t\le 10)\) — 表示测试用例的数量。接下来是测试用例的描述。

第一行包含两个整数 \(n,m\ (1\le n, m\le 2\times 10^5)\) — 表示天数和优惠券的数量。

第二行包含 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\ (1\le a_i \le 10^9)\) — 其中 \(a_i\) 表示第 \(i\) 天咖啡的价格。

接下来的 \(m\) 行,每行包含两个整数 \(r_i,w_i\ (1\le r_i\le n,\ 1\le w_i\le 10^9)\) — 表示第 \(i\) 张优惠券可以在前 \(r_i\) 使用,并且可以将价格减少 \(w_i\)

Output

对于每个测试用例,输出 \(n\) 个整数 — 第 \(i\) 个整数表示 Zayin 恰好选择 \(i\) 天购买咖啡时所花费的最少金额。

Sample

2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
-2 0 3 7 12 
-21 -18 -15 -11 -5 3 13 

Hint