Phi thuyền và kho vàng

Quân nổi dậy có $s$ phi thuyền, phi thuyền thứ $i$ có sức tấn công $a_i$.

Đế chế có $b$ căn cứ, căn cứ thứ $j$ có sức phòng thủ $d_j$ và chứa $g_j$ đơn vị vàng.

Một phi thuyền có sức tấn công $a$ có thể tấn công mọi căn cứ có sức phòng thủ $d\le a$ và lấy toàn bộ số vàng tại các căn cứ đó.

Với mỗi phi thuyền, hãy tính lượng vàng tối đa mà nó có thể lấy được (giả sử nó được phái đi một mình và các căn cứ chưa bị bất kỳ phi thuyền nào khác chạm tới).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $s$ và $b$.
• Dòng thứ hai chứa $s$ số nguyên $a_1,a_2,\dots ,a_s$ — sức tấn công của từng phi thuyền.
• $b$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_j$ và $g_j$ — sức phòng thủ và lượng vàng của căn cứ thứ $j$.

Dữ liệu ra

In ra $s$ số nguyên trên cùng một dòng, cách nhau bởi dấu cách, là lượng vàng tối đa mà mỗi phi thuyền lấy được, theo thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le s,b\le {10}^5$
• $0\le a_i\le {10}^9$
• $0\le d_j\le {10}^9$
• $0\le g_j\le {10}^4$

Ví dụ