Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $s$ spaceships, each with a certain attacking power $a$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $b$ bases, each with a certain defensive power $d$, and a certain amount of gold $g$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.


-----Input-----

The first line contains integers $s$ and $b$ ($1 \leq s, b \leq 10^5$), the number of spaceships and the number of bases, respectively.

The second line contains $s$ integers $a$ ($0 \leq a \leq 10^9$), the attacking power of each spaceship.

The next $b$ lines contain integers $d, g$ ($0 \leq d \leq 10^9$, $0 \leq g \leq 10^4$), the defensive power and the gold of each base, respectively.


-----Output-----

Print $s$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.


-----Example-----
Input
5 4
1 3 5 2 4
0 1
4 2
2 8
9 4

Output
1 9 11 9 11



-----Note-----

The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting


Solutions:
from bisect import bisect_right
(s, b) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
l = []
for _ in range(b):
	(d, g) = map(int, input().split(' '))
	l.append([d, g])
l = [[-1, 0]] + sorted(l)
for i in range(1, len(l)):
	l[i][1] += l[i - 1][1]
ans = []
value = [v[0] for v in l]
ans = [l[bisect_right(value, v) - 1][1] for v in a]
for aa in ans:
	print(aa, end=' ')


import bisect
(n, m) = map(int, input().split())
a = map(int, input().split())
(b, g) = map(list, zip(*[[0, 0]] + sorted((list(map(int, input().split())) for _ in range(m)))))
for i in range(m):
	g[i + 1] += g[i]
v = []
for x in a:
	i = bisect.bisect(b, x)
	v += (g[i - 1],)
print(' '.join(map(str, v)))


string_ = input()
(s, b) = string_.split()
s = int(s)
b = int(b)
string_ = input()
arr = string_.split()
arr = [int(x) for x in arr]
base = []
for i in range(b):
	string_ = input()
	(d, g) = string_.split()
	d = int(d)
	g = int(g)
	base.append((d, g))
base.sort()
pref = []
for i in range(b):
	if i == 0:
		pref.append(base[i][1])
	else:
		pref.append(pref[i - 1] + base[i][1])
for i in range(s):
	ans = 0
	(lef, r) = (0, b)
	while r - lef > 1:
		mid = int((r + lef) / 2)
		if base[mid][0] > arr[i]:
			r = mid
		else:
			lef = mid
	if lef == 0:
		if base[lef][0] <= arr[i]:
			ans += pref[lef]
	else:
		ans += pref[lef]
	print(ans, end=' ')


def Sort(sub_li):
	sub_li.sort(key=lambda x: x[0])
	return sub_li
o = input().rstrip().split(' ')
p = input().rstrip().split(' ')
l = []
q = []
w = []
S = []
D = []
for i in range(0, int(o[1])):
	g = input().rstrip().split(' ')
	D = []
	D.append(int(g[0]))
	D.append(int(g[1]))
	l.append(D)
l = Sort(l)
for i in range(0, len(l)):
	if i == 0:
		q.append(l[i][1])
	else:
		q.append(l[i][1] + q[len(q) - 1])
for i in range(0, len(p)):
	t = int(p[i])
	I = 0
	J = len(l) - 1
	V = -1
	while I <= J:
		m = (I + J) // 2
		if t >= l[m][0]:
			V = m
			I = m + 1
		else:
			J = m - 1
	if V == -1:
		print(0, end=' ')
	else:
		print(q[V], end=' ')


(s, b) = map(int, input().split())
spaceship = list(map(int, input().split()))
base = []
ans = []
for i in range(b):
	base.append([int(j) for j in input().split()])
base.sort()
gold = [base[0][1]]
for i in range(1, b):
	gold.append(gold[-1] + base[i][1])
for i in range(s):
	found = -1
	l = 0
	r = b - 1
	while l <= r:
		mid = l + (r - l) // 2
		if spaceship[i] >= base[mid][0]:
			found = mid
			l = mid + 1
		else:
			r = mid - 1
	if found == -1:
		ans.append(0)
	else:
		ans.append(gold[found])
print(*ans)


import sys
from operator import itemgetter

def main():
	solution_list = parse_input(get_input())
	for i in solution_list:
		print(i)

def get_input():
	input_list = []
	for line in sys.stdin:
		input_list.append(line.rstrip('\n'))
	return input_list

def parse_input(input_list):
	ship_list = [int(x) for x in input_list[1].split(' ')]
	base_list = sorted([[int(x) for x in y.split(' ')] for y in input_list[2:]], key=itemgetter(0))
	return solve(ship_list, base_list)

def solve(ship_list, base_list):
	solution_list = []
	sum_list = []
	base_d_list = [base_list[x][0] for x in range(len(base_list))]
	total = 0
	for base in base_list:
		total += base[1]
		sum_list.append(total)
	for ship in ship_list:
		if ship < base_d_list[0]:
			solution_list.append(0)
		elif ship >= base_d_list[-1]:
			solution_list.append(sum_list[-1])
		else:
			index = binary_search(base_d_list, 0, len(base_d_list) - 1, ship)
			solution_list.append(sum_list[index - 1])
	return solution_list

def binary_search(num_list, lower, upper, value):
	if lower > upper:
		if lower == len(num_list) and num_list[upper] != value:
			return False
		else:
			return lower
	mid = lower + (upper - lower) // 2
	if num_list[mid] > value:
		return binary_search(num_list, lower, mid - 1, value)
	else:
		return binary_search(num_list, mid + 1, upper, value)
main()


from bisect import bisect_right
int_arr = lambda : [int(x) for x in input().split()]
(nb_spaceship, nb_bases) = int_arr()
attack_power = int_arr()
attempt = [[-1, 0]] + sorted((int_arr() for _ in range(nb_bases)))
for i in range(1, nb_bases + 1):
	attempt[i][1] += attempt[i - 1][1]
v = [p[0] for p in attempt]
ans = [attempt[bisect_right(v, x) - 1][1] for x in attack_power]
print(*ans)


(a, b) = map(int, input().split())
z = [0] * a
f = sorted(([j, i] for (i, j) in enumerate(map(int, input().split()))))
k = sorted([list(map(int, input().split())) for i in range(b)])
(i, j, s) = (0, 0, 0)
while i < a:
	while j < b and f[i][0] >= k[j][0]:
		s += k[j][1]
		j += 1
	z[f[i][1]] = s
	i += 1
print(*z)


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(b):
	(x, y) = map(int, input().split())
	d.append((x, y, i + 1))
d.sort()
f = [d[0][1]]
for i in range(1, b):
	f.append(f[-1] + d[i][1])
for i in range(s):
	if d[0][0] > a[i]:
		print(0, end=' ')
	elif d[-1][0] <= a[i]:
		print(f[-1])
	else:
		L = 0
		R = b - 1
		while R - L > 1:
			m = (L + R) // 2
			if d[m][0] <= a[i]:
				L = m
			else:
				R = m
		print(f[L], end=' ')


def prefix_sums(array):
	res = [array[0]]
	for v in array[1:]:
		res.append(res[-1] + v)
	return res
(spaces, bases) = input().split()
spaceships = [int(a) for a in input().split()]
base_list = [[int(b) for b in input().split()] for base in range(int(bases))]
base_list = sorted(base_list)
defenses = [defense for (defense, _) in base_list]
gold = [gold for (_, gold) in base_list]
gold_prefix = prefix_sums(gold)
results = []
for attack in spaceships:
	(l, r) = (0, len(defenses) - 1)
	res = None
	while l <= r:
		mid = (l + r) // 2
		if attack >= defenses[mid]:
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	if res is None:
		results.append(0)
	else:
		results.append(gold_prefix[res])
print(' '.join(map(str, results)))


import bisect

def cummulative_sum(arr):
	acc = 0
	newarr = [[0, 0]]
	for (defence, gold) in arr:
		acc += gold
		if newarr[-1][0] == defence:
			newarr[-1][1] += gold
		else:
			newarr.append([defence, acc])
	return newarr
(spaceship_count, base_count) = map(int, input().strip().split())
spaceships = list(map(int, input().strip().split()))
bases = []
answer = []
for _ in range(base_count):
	(d, g) = map(int, input().strip().split())
	bases.append((d, g))
bases.sort()
bases_prefixes = cummulative_sum(bases)
for spaceship in spaceships:
	i = bisect.bisect_right(bases_prefixes, [spaceship, 10 ** 15])
	answer.append(bases_prefixes[i - 1][1])
print(*answer)


from bisect import bisect_right
from operator import itemgetter
(s, b) = map(int, input().split())
A = list(map(int, input().split()))
DG = [list(map(int, input().split())) for _ in range(b)]
DG.sort(key=itemgetter(0))
cumG = [0]
for (d, g) in DG:
	cumG.append(cumG[-1] + g)
D = list(map(itemgetter(0), DG))
Ans = []
for a in A:
	idx = bisect_right(D, a)
	Ans.append(cumG[idx])
print(*Ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()

def bs(a, k):
	l = 0
	h = len(a) - 1
	while l <= h:
		m = l + (h - l) // 2
		if a[m] <= k and (m == len(a) - 1 or a[m + 1] > k):
			return m
		elif a[m] <= k:
			l = m + 1
		else:
			h = m - 1
	return -1
(s, b) = map(int, input().split())
sp = [int(i) for i in input().split()]
d = {}
for i in range(b):
	(p, g) = map(int, input().split())
	try:
		d[p] += g
	except:
		d[p] = g
power = sorted(list(d.keys()))
pre = [d[power[0]]]
for i in range(1, len(power)):
	pre.append(pre[i - 1] + d[power[i]])
ans = 0
for i in sp:
	e = bs(power, i)
	if e != -1:
		ans = pre[e]
	else:
		ans = 0
	print(ans, end=' ')


def bs(num):
	low = 0
	high = b - 1
	while low < high:
		mid = (low + high) // 2
		if l[mid][0] <= num:
			low = mid + 1
		else:
			high = mid - 1
	if l[low][0] <= num:
		return low
	else:
		return low - 1
(n, b) = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(b):
	l.append(list(map(int, input().split())))
l.sort()
p = [l[0][1]]
for i in range(1, b):
	p.append(p[-1] + l[i][1])
for i in a:
	pos = bs(i)
	if pos == -1:
		print(0, end=' ')
	else:
		print(p[pos], end=' ')
print()


(s, b) = list(map(int, input().split(' ')))
y = list(map(int, input().split()))
c = []
for i in range(b):
	(d, g) = list(map(int, input().split(' ')))
	c.append([d, g])
c = sorted(c)
c2 = []
j = s1 = 0
while j < b:
	s1 = s1 + c[j][1]
	c2.append(s1)
	j += 1
c2.append(0)
count = []
for i in range(s):
	start = 0
	end = b - 1
	mid = (start + end) // 2
	while start <= end:
		if c[mid][0] <= y[i]:
			start = mid + 1
			end = end
			mid = (start + end) // 2
		else:
			start = start
			end = mid - 1
			mid = (start + end) // 2
	count.append(c2[end])
print(*count)


(s, b) = map(int, input().split())
a = [int(s) for s in input().split()]
dg = [[int(s) for s in input().split()] for i in range(b)]
dg.sort()
for i in range(1, b):
	dg[i][1] += dg[i - 1][1]
for i in a:
	left = 0
	right = b - 1
	if i < dg[0][0]:
		print(0)
		continue
	if i >= dg[-1][0]:
		print(dg[-1][1])
		continue
	while True:
		m = (left + right) // 2
		if left == m:
			print(dg[left][1], end=' ')
			break
		if dg[m][0] > i:
			right = m
		else:
			left = m


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
dg = []
for _ in range(b):
	(d, g) = map(int, input().split())
	dg.append([d, g])
dg.sort()
gpref = [0]
gsum = 0
for el in dg:
	gsum += el[1]
	gpref.append(gsum)
golds = []
for i in range(s):
	if a[i] >= dg[-1][0]:
		golds.append(gpref[-1])
	elif a[i] < dg[0][0]:
		golds.append(0)
	else:
		left = 0
		right = b
		while right - left > 1:
			mid = left + (right - left) // 2
			if a[i] >= dg[mid][0]:
				left = mid
			else:
				right = mid
		golds.append(gpref[left + 1])
print(*golds)


from bisect import bisect_right
(s, b) = map(int, input().split())
ships = list(map(int, input().split()))
bases = []
defence = []
gold = [0]
for _ in range(b):
	bases.append(tuple(map(int, input().split())))
bases.sort(key=lambda x: x[0])
for i in range(b):
	(d, g) = bases[i]
	defence.append(d)
	gold.append(gold[-1] + g)
print(*[gold[bisect_right(defence, ship)] for ship in ships])


from sys import setcheckinterval, stdin
setcheckinterval(1000)
iin = lambda : int(stdin.readline())
lin = lambda : list(map(int, stdin.readline().split()))
(s, b) = lin()
sa = lin()
ba = [lin() for i in range(b)]
ba.sort()
ans = []
sol = []
for (i, j) in ba:
	sol.append(i)
	ans.append(j)
for i in range(1, b):
	ans[i] += ans[i - 1]
from bisect import bisect_right
a = []
for i in sa:
	x = bisect_right(sol, i) - 1
	if x < 0:
		a.append(0)
	else:
		a.append(ans[x])
print(*a)


(s, b) = map(int, input().split())
spaceships = list(map(int, input().split()))
bases = [tuple(map(int, input().split())) for i in range(b)]
bases.sort()
sumbases = [bases[i][1] for i in range(b)]
for i in range(1, b):
	sumbases[i] += sumbases[i - 1]

def search_bases(strength):
	(l, r) = (0, b)
	while l < r:
		m = (l + r) // 2
		if bases[m][0] <= strength:
			l = m + 1
		else:
			r = m
	return l - 1

def res(x):
	i = search_bases(x)
	if i < 0:
		return 0
	else:
		return sumbases[i]
print(*tuple(map(res, spaceships)))


import bisect

def main():
	(s, b) = map(int, input().split())
	attack = list(map(int, input().split()))
	dist_defense = {}
	for i in range(b):
		(d, g) = map(int, input().split())
		if d not in dist_defense.keys():
			dist_defense[d] = g
		else:
			dist_defense[d] += g
	defense = []
	for i in dist_defense.keys():
		defense.append(i)
	defense.sort()
	dp = []
	for i in defense:
		if not dp:
			dp.append(dist_defense[i])
		else:
			dp.append(dp[-1] + dist_defense[i])
	gold = []
	for i in attack:
		index = bisect.bisect(defense, i) - 1
		if index == -1:
			gold.append(0)
			continue
		gold.append(dp[index])
	for i in gold:
		print(i, end=' ')
main()


from bisect import bisect_right

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	return -1
(s, b) = list(map(int, input().split()))
v = []
a = list(map(int, input().split()))
for i in range(b):
	v.append(tuple(map(int, input().split())))
v.sort()
summa = 0
c = []
for i in v:
	summa += i[1]
	c.append(summa)
mas = [i[0] for i in v]
for i in a:
	ind = find_le(mas, i)
	if ind == -1:
		print(0)
	else:
		print(c[ind], end=' ')


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
W = stdout.write
hg = lambda x, y: (y + x - 1) // x * x
(s, b) = R()
a = list(R())
v = []
for _ in range(b):
	v += (tuple(R()),)
v.sort(key=lambda x: x[0])
sm = [0]
for i in v:
	sm += (sm[-1] + i[1],)
for i in a:
	l = 0
	r = b - 1
	ans = 0
	while l <= r:
		m = (l + r) // 2
		if v[m][0] <= i:
			ans = max(ans, sm[m + 1])
			l = m + 1
		else:
			r = m - 1
	W(str(ans) + ' ')


(s, b) = map(int, input().split())
m = [int(s) for s in input().split()]
mas = []
for _ in range(b):
	mas.append(list(map(int, input().split())))
mas.sort()
for i in range(b - 1):
	mas[i + 1][1] += mas[i][1]
for i in m:
	left = -1
	right = b
	while right - left > 1:
		middle = (right + left) // 2
		if mas[middle][0] <= i:
			left = middle
		else:
			right = middle
	if left == -1:
		print(0, end=' ')
	else:
		print(mas[right - 1][1], end=' ')


T = 1
for _ in range(T):
	(n, m) = map(int, input().split())
	s = list(map(int, input().split()))
	s = list(((s[i], i) for i in range(n)))
	b = []
	for j in range(m):
		(d, r) = map(int, input().split())
		b.append((d, r))
	b.sort(key=lambda x: x[0])
	s.sort(key=lambda x: x[0])
	cnts = []
	for i in range(n):
		cnts.append(0)
	i = 0
	j = 0
	ans = 0
	while True:
		if s[i][0] >= b[j][0]:
			ans += b[j][1]
			cnts[s[i][1]] += b[j][1]
			j += 1
		else:
			i += 1
			try:
				cnts[s[i][1]] = ans
			except:
				pass
		if i >= n or j >= m:
			break
	while i < n:
		cnts[s[i][1]] = ans
		i += 1
	for i in cnts:
		print(i, end=' ')
	print()


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(s, b) = map(int, input().split())
spaceship = list(map(int, input().split()))
base = []
ans = []
for i in range(b):
	base.append([int(j) for j in input().split()])
base.sort()
gold = [base[0][1]]
for i in range(1, b):
	gold.append(gold[-1] + base[i][1])
for i in range(s):
	found = -1
	l = 0
	r = b - 1
	while l <= r:
		mid = l + (r - l) // 2
		if spaceship[i] >= base[mid][0]:
			found = mid
			l = mid + 1
		else:
			r = mid - 1
	if found == -1:
		ans.append(0)
	else:
		ans.append(gold[found])
print(*ans)


from bisect import *
(s, b) = map(int, input().split())
spaceships = list(map(int, input().split()))
bases = []
for x in range(b):
	bases.append(list(map(int, input().split())))
bases.sort(key=lambda x: x[0])
val = bases[0][1]
for i in range(1, b):
	bases[i][1] += val
	val = bases[i][1]
(defence, gold) = map(list, zip(*bases))
for i in spaceships:
	index = bisect_right(defence, i) - 1
	if index < 0:
		print(0, end=' ')
		continue
	print(gold[index], end=' ')


(s, b) = map(int, input().split())
a = [*map(int, input().split())]
di = {}
from sys import stdin
for _ in range(b):
	(d, g) = map(int, stdin.readline().split())
	if di.get(d) == None:
		di[d] = 0
	di[d] += g
lst = list(di.keys())
lst.sort()
for (i, x) in enumerate(lst[1:]):
	di[x] += di[lst[i]]
res = []
app = res.append
from bisect import bisect
for (i, x) in enumerate(a):
	item = bisect(lst, x)
	if item == 0:
		if lst[0] == x:
			app(di[lst[0]])
		else:
			app(0)
	else:
		app(di[lst[item - 1]])
print(*res)


(s, b) = map(int, input().split(' '))
ships = map(int, input().split(' '))
bases = [tuple(map(int, input().split(' '))) for _ in range(b)]
bases.sort()
gold = [0] * (b + 1)
for i in range(b):
	gold[i + 1] = gold[i] + bases[i][1]

def find(x, inf, sup):
	while inf < sup:
		mid = (inf + sup) // 2
		if bases[mid][0] <= x:
			inf = mid + 1
		else:
			sup = mid
	return sup - 1
attacks = [0] * s
for (i, ship) in enumerate(ships):
	attacks[i] = gold[find(ship, 0, b) + 1]
print(' '.join(map(str, attacks)))


import bisect
(s, b) = map(int, input().split())
l = list(map(int, input().split()))
attack = []
for j in range(b):
	(x, y) = map(int, input().split())
	attack.append([x, y])
attack.sort()
(defense, gold) = zip(*attack)
total = [gold[0]]
for j in range(1, b):
	total.append(total[j - 1] + gold[j])
for j in range(s):
	val = l[j]
	index = bisect.bisect(defense, val)
	if index == 0:
		print(0, end=' ')
	else:
		print(total[index - 1], end=' ')


(s_cnt, b_cnt) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = []
for i in range(b_cnt):
	(d, g) = list(map(int, input().split()))
	b.append((d, g))
b.sort()
idx = [i for i in range(s_cnt)]
idx.sort(key=lambda i: a[i])
ans = [0] * s_cnt
(s, j) = (0, 0)
for i in range(s_cnt):
	while j < b_cnt and b[j][0] <= a[idx[i]]:
		s += b[j][1]
		j += 1
	ans[idx[i]] = s
print(*ans)


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z
(m, n) = map(int, input().split())
l = list(map(int, input().split()))
ans = [0] * m
ind = [i for i in range(m)]
ind = sort_list(ind, l)
l.sort()
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
b = sort_list(b, a)
a.sort()
t = 0
for i in range(m):
	ans[i] = ans[i - 1]
	if t == n:
		continue
	while a[t] <= l[i]:
		ans[i] += b[t]
		t += 1
		if t == n:
			break
ans = sort_list(ans, ind)
print(*ans, sep=' ')


from sys import stdin, stdout

def main():
	(s, b) = map(int, stdin.readline().strip().split())
	a = [int(num) for num in stdin.readline().strip().split()]
	req = []
	for __ in range(b):
		(d, g) = map(int, stdin.readline().strip().split())
		req.append((d, g))
	req = sorted(req, key=lambda pair: pair[0], reverse=False)
	p_sum = []
	for i in req:
		if not p_sum:
			p_sum.append(i[1])
		else:
			p_sum.append(i[1] + p_sum[-1])
	outputs = []
	for target in a:
		(l, r) = (-1, b)
		while l + 1 < r:
			m = l + (r - l) // 2
			if req[m][0] <= target:
				l = m
			else:
				r = m
		if l != -1:
			outputs.append(f'{p_sum[l]}')
		else:
			outputs.append('0')
	stdout.write(' '.join(outputs))
main()


import bisect
import functools
import math
import sys
from collections import defaultdict
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

def main():
	(s, b) = rt()
	a = rl()
	bases = []
	for _ in range(b):
		bases.append(tuple(map(int, input().split())))
	bases.sort()
	defense = [x[0] for x in bases]
	pref = [0] * b
	for i in range(b):
		if i == 0:
			pref[i] = bases[i][1]
		else:
			pref[i] = pref[i - 1] + bases[i][1]
	res = []
	for att in a:
		pos = bisect.bisect_right(defense, att)
		res.append(pref[pos - 1] if pos > 0 else 0)
	print(*res)
main()


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
d = [list(map(int, input().split())) for _ in range(b)]
d.sort(key=lambda f: f[0])
for i in range(1, b):
	d[i][1] += d[i - 1][1]
d = {k: v for (k, v) in d}
k = list(d.keys())
from bisect import bisect_right as br
for ship in a:
	key = br(k, ship)
	ans = d[k[key - 1]] if key else 0
	print(ans, end=' ')


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	for i in range(2, len(primes)):
		if primes[i] == True:
			prime.append(i)
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def NcR(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = math.gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p

def Log2(x):
	if x == 0:
		return False
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))
(s, b) = map(int, input().split())
a = list(map(int, input().split()))
ans = []
gold = []
for i in range(b):
	(d, g) = map(int, input().split())
	ans.append([d, g])
ans.sort()
prefix = [ans[0][1]]
for i in range(1, len(ans)):
	prefix.append(prefix[-1] + ans[i][1])
for i in range(0, len(a)):
	l = 0
	cur = 0
	r = len(ans) - 1
	while l <= r:
		mid = (l + r) // 2
		if ans[mid][0] <= a[i]:
			l = mid + 1
			cur = prefix[mid]
		else:
			r = mid - 1
	gold.append(cur)
print(*gold)


def bins(a, k, n1):
	(l, h) = (0, n1 - 1)
	while l <= h:
		m = (l + h) // 2
		if l == h:
			return m
		elif a[m][0] <= k:
			l = m + 1
		else:
			h = m - 1
	return l
(n, n1) = map(int, input().split())
sp = list(map(int, input().split()))
de = []
s = 0
gosum = []
for i in range(n1):
	(d, g) = map(int, input().split())
	de += [[d, g]]
de.sort()
for i in range(n1):
	s += de[i][1]
	gosum += [s]
for i in range(n):
	ind = bins(de, sp[i], n1)
	if de[ind][0] > sp[i] and ind != 0:
		print(gosum[ind - 1], end=' ')
	elif ind == 0 and de[ind][0] > sp[i]:
		print(0, end=' ')
	else:
		print(gosum[ind], end=' ')


(n, b) = [int(a) for a in input().split(' ')]
p_arr = [int(p) for p in input().split(' ')]
b_arr = []
n_p_arr = []
for i in range(0, len(p_arr)):
	n_p_arr.append([p_arr[i], i + 1])
sorted_n_p_arr = sorted(n_p_arr, key=lambda x: x[0], reverse=True)
for i in range(0, b):
	c = input().split(' ')
	b_arr.append([int(a) for a in c])
sorted_b_arr = sorted(b_arr, key=lambda x: x[0], reverse=True)
result_arr = []
merge_arr = []
a_d = dict()
for i in p_arr:
	a_d[i] = False
for i in b_arr:
	merge_arr.append([i[0], i[1]])
	a_d[i[0]] = True
for i in p_arr:
	if a_d[i] != True:
		merge_arr.append([i, -1])
s_merged_arr = sorted(merge_arr, key=lambda x: x[0])
if s_merged_arr[0][1] != -1:
	t_c = s_merged_arr[0][1]
else:
	t_c = 0
for i in range(1, len(s_merged_arr)):
	if s_merged_arr[i][1] == -1:
		s_merged_arr[i][1] = t_c
	else:
		t_c = t_c + s_merged_arr[i][1]
		s_merged_arr[i][1] = t_c
	a_d[s_merged_arr[i][0]] = t_c
res = []
for i in p_arr:
	if a_d[i] == False:
		res.append(0)
	else:
		res.append(a_d[i])
print(' '.join([str(a) for a in res]))


(n, m) = map(int, input().split())
a = sorted([(int(x), y) for (x, y) in zip(input().split(), range(n))])
b = []
for _ in range(m):
	b.append(list(map(int, input().split())))
b = sorted(b)
p1 = 0
p2 = 0
s = 0
ans = [0 for _ in range(len(a))]
while p1 < len(a) and p2 < len(b):
	if a[p1][0] >= b[p2][0]:
		s += b[p2][1]
		p2 += 1
	else:
		ans[a[p1][1]] = s
		p1 += 1
while p1 < len(a):
	ans[a[p1][1]] = s
	p1 += 1
print(' '.join(list(map(str, ans))))


def sortFunc(item):
	return item['size']

def binary_search(array, target):
	lower = 0
	upper = len(array)
	while lower < upper:
		x = lower + (upper - lower) // 2
		val = array[x]['size']
		if target == val:
			if x != len(array) - 1 and val == array[x + 1]:
				lower = x
				continue
			return x
		elif target > val:
			if lower == x:
				break
			lower = x
		elif target < val:
			upper = x
			if upper == 0 and lower == 0:
				x -= 1
	return x
lengthInfo = input()
lengthInfo = lengthInfo.split(' ')
sLen = int(lengthInfo[0])
baseLen = int(lengthInfo[1])
spaces = input()
spaces = spaces.split(' ')
bases = []
golds = 0
for i in range(0, baseLen):
	inputBase = input()
	inputBase = inputBase.split(' ')
	bases.append({'size': int(inputBase[0]), 'gold': int(inputBase[1])})
bases.sort(key=sortFunc)
golds = 0
for i in range(0, baseLen):
	golds += bases[i]['gold']
	bases[i]['gold'] = golds
for space in spaces:
	a = binary_search(bases, int(space))
	if a == -1:
		print(0)
		continue
	print(bases[a]['gold'])


import bisect
from collections import defaultdict
(s, b) = map(int, input().split())
a = [int(x) for x in input().split()]
d = defaultdict(int)
l = []
for i in range(b):
	(x, y) = map(int, input().split())
	l += [(x, y)]
l.sort(key=lambda x: x[0])
res = []
for i in range(b):
	if i == 0:
		res += [l[i][1]]
	else:
		res += [res[-1] + l[i][1]]
for i in range(s):
	t = a[i]
	I = 0
	J = len(l) - 1
	V = -1
	while I <= J:
		m = (I + J) // 2
		if t >= l[m][0]:
			V = m
			I = m + 1
		else:
			J = m - 1
	if V == -1:
		print(0, end=' ')
	else:
		print(res[V], end=' ')


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right, bisect
(s, b) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
bases = []
for _ in range(b):
	bases.append(list(map(int, stdin.readline().split())))
bases.sort()
prefixsum = [0]
curr = 0
defense = []
for (i, j) in bases:
	defense.append(i)
	curr += j
	prefixsum.append(curr)
for i in a:
	print(prefixsum[bisect(defense, i)], end=' ')
print()


import bisect
(s, b) = map(int, input().split())
a = list(map(int, input().split()))
base = []
bi = []
for i in range(b):
	(p, q) = map(int, input().split())
	base.append((p, q))
	bi.append(p)

def sortFirst(val):
	return val[0]
base.sort(key=sortFirst)
bi.sort()
gold = [base[0][1]]
for i in range(1, b):
	gold.append(base[i][1] + gold[i - 1])
ans = []
for i in a:
	ind = bisect.bisect(bi, i, 0, b - 1)
	if ind == 0:
		if bi[ind] > i:
			ans.append(0)
		else:
			ans.append(gold[0])
	elif ind == b - 1 and bi[ind] <= i:
		ans.append(gold[ind])
	else:
		ans.append(gold[ind - 1])
print(*ans)


import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor
from copy import deepcopy
from itertools import accumulate
from collections import Counter
import math
from functools import reduce
from bisect import bisect_right
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def ii():
	return int(input())

def mi():
	return map(int, input().rstrip().split())

def lmi():
	return list(map(int, input().rstrip().split()))

def li():
	return list(input().rstrip())

def debug(x):
	print('debug: ', x, file=sys.stderr)

class BIT:

	def __init__(self, x, d=0):
		if isinstance(x, int):
			self.size = x
			self.tree = [d for _ in range(self.size + 1)]
		elif isinstance(x, list):
			self.size = len(x)
			self.tree = [d for _ in range(self.size + 1)]
			self.build(x)
		else:
			raise TypeError

	def build(self, arr):
		if isinstance(arr, list):
			raise TypeError
		for (num, x) in enumerate(arr):
			self.add0(num, x)

	def sum(self, i):
		s = self.tree[0]
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, a):
		if i == 0:
			return
		while i <= self.size:
			self.tree[i] += a
			i += i & -i

	def bisect_left(self, w):
		if w <= 0:
			return 0
		x = 0
		r = 1
		while r < self.size:
			r <<= 1
		k = r
		while k > 0:
			if x + k <= self.size and self.tree[x + k] < w:
				w -= self.tree[x + k]
				x += k
			k >>= 1
		return x + 1

	def query(self, l, r):
		return self.sum(r - 1) - self.sum(l - 1)

	def sum0(self, i):
		return self.sum(i + 1)

	def add0(self, i, a):
		self.add(i + 1, a)

	def query0(self, l, r):
		return self.sum(r) - self.sum(l)

	def __getitem__(self, item):
		_tmp = item.indices(self.size + 1)
		return [self.sum(i) - self.sum(i - 1) for i in range(_tmp[0], _tmp[1], _tmp[2])]

	def __str__(self):
		return str(self[1:self.size + 1])

def main():
	(s, b) = mi()
	a = lmi()
	d = []
	g = []
	for i in range(b):
		(_d, _g) = mi()
		d.append(_d)
		g.append(_g)
	tmp = [(d[i], g[i]) for i in range(b)]
	tmp.sort(key=lambda x: x[0])
	d.sort()
	bit = BIT(b)
	for i in range(b):
		bit.add0(i, tmp[i][1])
	for i in range(s):
		tmp = bisect_right(d, a[i])
		print(bit.sum(tmp), end=' ')
	print()

def __starting_point():
	main()
__starting_point()


import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor
from copy import deepcopy
from itertools import accumulate
from collections import Counter
import math
from functools import reduce
from bisect import bisect_right
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def ii():
	return int(input())

def mi():
	return map(int, input().rstrip().split())

def lmi():
	return list(map(int, input().rstrip().split()))

def li():
	return list(input().rstrip())

def debug(x):
	print('debug: ', x, file=sys.stderr)

class SegTree:

	def __init__(self, n: int, function, unity: int):
		self.UNITY = unity
		self.fn = function
		self.n = n
		self.SIZE_R = 1
		while self.SIZE_R < n:
			self.SIZE_R *= 2
		self.dat = [self.UNITY for _ in range(self.SIZE_R * 2 + 10)]

	def set(self, a: int, v: int):
		self.dat[self.SIZE_R + a] = v

	def build(self):
		for k in range(self.SIZE_R - 1, 0, -1):
			self.dat[k] = self.fn(self.dat[k * 2], self.dat[k * 2 + 1])

	def make_tree(self, arr: list):
		if self.n != len(arr):
			raise IndexError
		for i in range(len(arr)):
			self.set(i, arr[i])
		self.build()

	def update(self, a, v):
		k = self.SIZE_R + a
		self.dat[k] = v
		while k > 1:
			k = k // 2
			self.dat[k] = self.fn(self.dat[k * 2], self.dat[k * 2 + 1])

	def query(self, a, b):
		vleft = self.UNITY
		vright = self.UNITY
		left = a + self.SIZE_R
		right = b + self.SIZE_R
		while left < right:
			if left & 1:
				vleft = self.fn(vleft, self.dat[left])
				left += 1
			if right & 1:
				right -= 1
				vright = self.fn(self.dat[right], vright)
			left >>= 1
			right >>= 1
		return self.fn(vleft, vright)

	def __getitem__(self, k):
		return self.dat[k + self.SIZE_R]

def main():
	(s, b) = mi()
	a = lmi()
	d = []
	g = []
	for i in range(b):
		(_d, _g) = mi()
		d.append(_d)
		g.append(_g)
	tmp = [(d[i], g[i]) for i in range(b)]
	tmp.sort(key=lambda x: x[0])
	d.sort()
	bit = SegTree(b, lambda a, b: a + b, 0)
	for i in range(b):
		bit.set(i, tmp[i][1])
	bit.build()
	for i in range(s):
		tmp = bisect_right(d, a[i])
		print(bit.query(0, tmp), end=' ')
	print()
main()


def bs(a, k):
	l = 0
	h = len(a) - 1
	while l <= h:
		m = l + (h - l) // 2
		if a[m] <= k and (m == len(a) - 1 or a[m + 1] > k):
			return m
		elif a[m] <= k:
			l = m + 1
		else:
			h = m - 1
	return -1
(s, b) = map(int, input().split())
sp = [int(i) for i in input().split()]
d = {}
for i in range(b):
	(p, g) = map(int, input().split())
	try:
		d[p] += g
	except:
		d[p] = g
power = sorted(list(d.keys()))
pre = [d[power[0]]]
for i in range(1, len(power)):
	pre.append(pre[i - 1] + d[power[i]])
ans = 0
for i in sp:
	e = bs(power, i)
	if e != -1:
		ans = pre[e]
	else:
		ans = 0
	print(ans, end=' ')


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(s, b) = mp()
arr = lmp()
tmp = [tuple(mp()) for i in range(b)]
tmp.sort()
(d, g) = ([], [0])
for (x, y) in tmp:
	d.append(x)
	g.append(g[-1] + y)
for i in arr:
	ind = br(d, i)
	print(g[ind], end=' ')
print()


(n, m) = list(map(int, input().split()))
d = list(map(int, input().split()))
l = []
for i in range(n):
	l.append([d[i], i])
l.sort()
l2 = []
for i in range(m):
	(a, b) = list(map(int, input().split()))
	l2.append([a, b])
l2.sort()
s = 0
j = 0
r = [0] * n
for i in range(n):
	while j < m and l2[j][0] <= l[i][0]:
		s += l2[j][1]
		j += 1
	r[l[i][1]] = s
print(' '.join(map(str, r)))


def bs(num):
	low = 0
	high = b - 1
	while low < high:
		mid = (low + high) // 2
		if bases[mid][0] <= num:
			low = mid + 1
		else:
			high = mid - 1
	if bases[low][0] <= num:
		return low
	else:
		return low - 1
(n, b) = map(int, input().split())
ar = list(map(int, input().split()))
bases = []
summ = 0
for i in range(b):
	bases.append(list(map(int, input().split())))
bases.sort()
gold = [bases[0][1]]
for i in range(1, b):
	gold.append(gold[-1] + bases[i][1])
ans = []
for i in ar:
	pos = bs(i)
	if pos != -1:
		ans.append(gold[pos])
	else:
		ans.append(0)
print(*ans)


from bisect import *
(s, b) = map(int, input().split())
a = list(map(int, input().split()))
ar = []
for i in range(b):
	(d, g) = map(int, input().split())
	ar.append((d, g))
ar.sort()
pref = [0]
for i in range(b):
	pref.append(pref[-1] + ar[i][1])
for i in range(s):
	x = a[i]
	l = 0
	r = b
	while l < r:
		m = (l + r) // 2
		if ar[m][0] <= x:
			l = m + 1
		else:
			r = m
	print(pref[r], end=' ')
print()


import operator

def search(dgs, power):
	i = 0
	k = 0
	j = len(dgs) - 1
	while i <= j:
		k = (j + i) // 2
		if dgs[k][0] <= power and (k == j or (k < j and dgs[k + 1][0] > power)):
			return k
		if dgs[k][0] < power:
			i = k + 1
		elif dgs[k][0] > power:
			j = k - 1
	return -1

def get_index(gs, dgs, p):
	i = search(dgs, p)
	return gs[i] if i >= 0 else 0
(ships, bases) = list(map(int, input().split()))
powers = list(map(int, input().split()))
dgs = [list(map(int, input().split())) for b in range(bases)]
dgs.sort(key=operator.itemgetter(0))
gs = [dgs[0][1]]
for i in range(1, len(dgs)):
	gs.append(dgs[i][1] + gs[i - 1])
print(*[get_index(gs, dgs, p) for p in powers])


(s, b) = map(int, input().split())
l = list(map(int, input().split()))
base = []
for _ in range(b):
	(a, c) = map(int, input().split())
	base.append((a, c))
base.sort()
res = []
kuld = 0
klist = []
for j in range(b):
	kuld = kuld + base[j][1]
	klist.append(kuld)
for i in range(s):
	if l[i] < base[0][0]:
		res.append(0)
	else:
		left = 0
		right = b
		while right - left > 1:
			mid = left + (right - left) // 2
			if l[i] >= base[mid][0]:
				left = mid
			else:
				right = mid
		res.append(klist[left])
print(*res)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def bst(a2, n, key):
	l = 0
	r = n - 1
	ans = -1
	while l <= r:
		mid = (l + r) // 2
		if a2[mid][0] > key:
			r = mid - 1
		else:
			l = mid + 1
			ans = mid
	return ans

def Solution(a1, a2, s, b):
	prefix = [0]
	a2 = sorted(a2, key=lambda x: x[0])
	for v in a2:
		prefix.append(prefix[-1] + v[1])
	for i in range(s):
		idx = bst(a2, b, a1[i])
		if idx == -1:
			print(0, end=' ')
		else:
			print(prefix[idx + 1], end=' ')
	print()

def main():
	(s, b) = get_ints_in_variables()
	a1 = get_ints_in_list()
	a2 = [get_ints_in_list() for _ in range(b)]
	Solution(a1, a2, s, b)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bsl
(ship, b) = map(int, input().split())
vals = list(map(int, input().split()))
inf = []
for s in range(b):
	(d, g) = map(int, input().split())
	inf.append((d, g))
inf.sort(key=lambda x: x[0])
prefsum = [inf[0][1]]
for s in range(1, b):
	prefsum.append(prefsum[-1] + inf[s][1])
defe = [k[0] for k in inf]
ans = []
for s in range(ship):
	ind = min(bsl(defe, vals[s]), b - 1)
	if defe[ind] > vals[s]:
		ind -= 1
	if ind == -1:
		ans.append(0)
	else:
		ans.append(prefsum[ind])
print(*ans)


import bisect
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
s = []
for i in range(m):
	(a, b) = map(int, input().split())
	s.append([a, b])
k = sorted(s)
dp = []
s = []
c = 0
for i in range(len(k)):
	s.append(k[i][0])
	c += k[i][1]
	dp.append(c)
for i in range(n):
	p = bisect.bisect(s, l[i])
	if p == 0:
		print(0, end=' ')
	else:
		print(dp[p - 1], end=' ')
print()


from sys import stdin, stdout

def rsingle_int():
	return int(stdin.readline().rstrip())

def rmult_int():
	return [int(x) for x in stdin.readline().rstrip().split()]

def r_str():
	return stdin.readline().rstrip()

def rsingle_char():
	return stdin.read(1)

def main():
	(s, b) = rmult_int()
	a = rmult_int()
	a_order = a.copy()
	a.sort()
	a_g = {}
	for el in a:
		a_g[el] = 0
	ds = []
	d_g = {}
	for i in range(b):
		(d, g) = rmult_int()
		if d in d_g:
			d_g[d] += g
		else:
			d_g[d] = g
			ds.append(d)
	ds.sort()
	ds_len = len(ds)
	acc = 0
	d_i = 0
	for el in a:
		while d_i < ds_len and ds[d_i] <= el:
			acc += d_g[ds[d_i]]
			d_i += 1
		a_g[el] = acc
	out = []
	for el in a_order:
		out.append(int(a_g[el]))
	print(*out)
main()


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(s):
	a[i] = [a[i], i, None]
bases = []
for i in range(b):
	(d, g) = map(int, input().split())
	bases.append((d, g))
bases.sort()
a.sort()
j = 0
count = 0
for i in range(b):
	while j < s and a[j][0] < bases[i][0]:
		a[j][2] = count
		j += 1
	if j == s:
		break
	count += bases[i][1]
	if i == b - 1:
		if j < s and a[j][0] >= bases[i][0]:
			r = j
			for j in range(r, s):
				a[j][2] = count
a.sort(key=lambda x: x[1])
a = [x[2] for x in a]
print(*a)


def bin_search(list, target):
	(L, R) = (0, int(bases) - 1)
	while L <= R:
		mid = (L + R) // 2
		if list[mid] <= target:
			L = mid + 1
		else:
			R = mid - 1
	return L
(spaces, bases) = input().split()
spaceships = [int(a) for a in input().split()]
base_list = sorted([[int(b) for b in input().split()] for base in range(int(bases))])
gold = [g for (_, g) in base_list]
defense = [d for (d, _) in base_list]
total_gold = []
tot = 0
for element in gold:
	tot += element
	total_gold.append(tot)
total = []
for ship in spaceships:
	base_number = bin_search(defense, ship)
	if base_number == 0:
		total.append(0)
	else:
		total.append(total_gold[base_number - 1])
print(*total, sep=' ')


kq = []
a = []
d = []

def at(enum):
	return enum[1]

def defen(enum):
	return enum[0]
st = input()
c = st.split(' ')
s = int(c[0])
b = int(c[1])
st = input()
c = st.split(' ')
for i in range(0, s):
	x = int(c[i])
	a.append((i, x))
for i in range(0, s):
	kq.append(0)
for i in range(0, b):
	st = input()
	c = st.split(' ')
	x = int(c[0])
	y = int(c[1])
	d.append((x, y))
a.sort(reverse=False, key=at)
d.sort(reverse=False, key=defen)
j = 0
sum = 0
for i in range(0, s):
	if j == b:
		kq[a[i][0]] = sum
	else:
		while a[i][1] >= d[j][0] and j < b:
			sum = sum + d[j][1]
			j = j + 1
			if j == b:
				break
		kq[a[i][0]] = sum
delim = ' '
k = []
for x in kq:
	p = str(x)
	k.append(p)
print(delim.join(k))


import sys
from copy import deepcopy
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def ii():
	return int(input())

def mi():
	return map(int, input().rstrip().split())

def lmi():
	return list(map(int, input().rstrip().split()))

def li():
	return list(input().rstrip())

def debug(x):
	print('debug:', x, file=sys.stderr)

class CumulativeSum:

	def __init__(self, arr: list):
		self.data = deepcopy(arr)
		for i in range(1, len(self.data)):
			self.data[i] += self.data[i - 1]

	def _query(self, k: int) -> int:
		if k < 0:
			return 0
		else:
			return self.data[min(k, len(self.data) - 1)]

	def query(self, l: int, r: int) -> int:
		if l > r:
			return 0
		else:
			return self._query(r - 1) - self._query(l - 1)

	def __str__(self):
		return str(self.data)

	def __getitem__(self, k):
		return self.data[k]

class CumulativeXor:

	def __init__(self, arr: list, function=lambda a, b: a ^ b):
		self.data = deepcopy(arr)
		self.fn = function
		for i in range(1, len(self.data)):
			self.data[i] = self.fn(self.data[i], self.data[i - 1])

	def _query(self, k: int) -> int:
		if k < 0:
			return 0
		else:
			return self.data[min(k, len(self.data) - 1)]

	def query(self, l: int, r: int) -> int:
		if l > r:
			return 0
		else:
			return self.fn(self._query(r - 1), self._query(l - 1))

	def __str__(self):
		return str(self.data)

	def __getitem__(self, k):
		return self.data[k]
from bisect import bisect_right

def CF1184_B1():
	(s, b) = mi()
	a = lmi()
	d = []
	g = []
	for i in range(b):
		(_d, _g) = mi()
		d.append(_d)
		g.append(_g)
	tmp = [(d[i], g[i]) for i in range(b)]
	tmp.sort(key=lambda x: x[0])
	d.sort()
	bit = CumulativeSum([tmp[i][1] for i in range(b)])
	for i in range(s):
		tmp = bisect_right(d, a[i])
		print(bit.query(0, tmp), end=' ')
	print()
CF1184_B1()


import bisect
(s, b) = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(b):
	d.append(list(map(int, input().split())))
d = sorted(d)
c = []
p = []
for i in range(len(d)):
	c.append(d[i][0])
	p.append(d[i][1])
k = [p[0]]
for i in range(1, len(p)):
	k.append(k[-1] + p[i])
for i in range(len(a)):
	l = bisect.bisect_right(c, a[i])
	if l == 0:
		print(0, end=' ')
	else:
		print(k[l - 1], end=' ')


from sys import stdin
from bisect import bisect_right as br
input = stdin.readline
(s, b) = map(int, input().split())
sp = list(map(int, input().split()))
bp = []
for i in range(b):
	bp.append(list(map(int, input().split())))
c = [0] * b
bp.sort()
for i in range(1, b):
	bp[i][1] += bp[i - 1][1]
an = [0] * s
for i in range(s):
	m = br(bp, [sp[i]])
	if m < b and bp[m][0] > sp[i]:
		m -= 1
	elif m == b:
		m -= 1
	if m >= 0:
		an[i] = bp[m][1]
	else:
		an[i] = 0
print(*an)


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
dg = []
d = {}
for i in range(s):
	if a[i] not in d:
		d[a[i]] = [i]
	else:
		d[a[i]].append(i)
for _ in range(b):
	dg.append(list(map(int, input().split())))
a.sort()
dg.sort()
j = 0
prev = 0
ans = []
for i in range(s):
	while j < b and dg[j][0] <= a[i]:
		prev += dg[j][1]
		j += 1
	ans.append(prev)
fans = [0] * s
for i in range(s):
	for j in d[a[i]]:
		fans[j] = ans[i]
for i in fans:
	print(i, end=' ')


def naiveSolve():
	return

def main():
	(n, m) = readIntArr()
	a = readIntArr()
	d = []
	g = []
	for _ in range(m):
		(dd, gg) = readIntArr()
		d.append(dd)
		g.append(gg)
	idxByDef = list(range(m))
	idxByDef.sort(key=lambda i: d[i])
	p = [0] * m
	for i in idxByDef:
		p[i] = g[idxByDef[i]]
	for i in range(1, m):
		p[i] += p[i - 1]
	ans = [0] * n
	for i in range(n):
		atk = a[i]
		j = -1
		b = m
		while b > 0:
			while j + b < m and d[idxByDef[j + b]] <= atk:
				j += b
			b //= 2
		if j == -1:
			ans[i] = 0
		else:
			ans[i] = p[j]
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(r):
	print('? {}'.format(r))
	sys.stdout.flush()
	return readIntArr()

def answerInteractive(adj, n):
	print('!')
	for u in range(1, n + 1):
		for v in adj[u]:
			if v > u:
				print('{} {}'.format(u, v))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
input = lambda : sys.stdin.readline().strip()
from bisect import bisect_right
(s, b) = map(int, input().split())
ls = list(map(int, input().split()))
d = {}
for i in range(b):
	(a, b) = map(int, input().split())
	try:
		d[a] += b
	except:
		d[a] = b
keys = list(d.keys())
keys.sort()
Sum = 0
for i in keys:
	Sum += d[i]
	d[i] = Sum
for i in ls:
	if bisect_right(keys, i) != 0:
		print(d[keys[bisect_right(keys, i) - 1]], end=' ')
	else:
		print(0, end=' ')
print()


from bisect import bisect_right as bi
(s, b) = list(map(int, input().split()))
a = list(map(int, input().split()))
e = []
c = []
for i in range(b):
	(d, g) = list(map(int, input().split()))
	e.append(d)
	c.append([d, g])
e.sort()
c.sort()
d = 0
f = []
for i in range(b):
	c[i] = c[i][1]
	d += c[i]
	f.append(d)
d = []
for i in range(s):
	c = bi(e, a[i])
	if c == 0:
		d.append(0)
	else:
		d.append(f[c - 1])
print(*d)


import bisect
from collections import OrderedDict
(a, b) = list(map(int, input().split()))
aray = list(map(int, input().split()))
dic = {}
ans = OrderedDict()
max = 0
min = 55555555555
summ = 0
arr = []
answer = []
for x in range(b):
	(c, d) = list(map(int, input().split()))
	if c not in dic:
		dic[c] = [d]
		arr.append(c)
	else:
		dic[c].append(d)
	if c > max:
		max = c
	if c < min:
		min = c
arr.sort()
for it in arr:
	summ += sum(dic[it])
	ans[it] = summ
for it in aray:
	if it in ans:
		answer.append(ans[it])
	elif it < min:
		answer.append(0)
	elif it >= max:
		answer.append(ans[max])
	else:
		ind = bisect.bisect_left(arr, it)
		answer.append(ans[arr[ind - 1]])
print(*answer)


from sys import stdin, stdout
from bisect import bisect_right as br
from bisect import bisect_left as bl
from bisect import insort_left as il
from math import gcd
(n, m) = map(int, stdin.readline().split())
ship = [int(i) for i in stdin.readline().split()]
lst = [[-1, 0]]
for i in range(m):
	(a, b) = map(int, stdin.readline().split())
	lst += [[a, b]]
lst.sort()
temp = lst[0]
for i in lst[1:]:
	i[1] += temp[1]
	temp = i
for i in ship:
	stdout.write(str(lst[br(lst, [i, 10 ** 18]) - 1][1]) + ' ')


(s, b) = map(int, input().split())
a = list(map(int, input().split()))
z = [[-1, 0]] + sorted((list(map(int, input().split())) for _ in range(b)))
for i in range(1, b + 1):
	z[i][1] += z[i - 1][1]
v = [p[0] for p in z]

def binary_search(v, x):
	(l, r) = (0, len(v) - 1)
	while l <= r:
		m = l + r >> 1
		if v[m] > x:
			r = m - 1
		else:
			l = m + 1
	return r + 1
res = [z[binary_search(v, i) - 1][1] for i in a]
print(*res)


import os
import sys
from io import BytesIO, IOBase

def main():
	(s, b) = map(int, input().split())
	ships = [(x, i) for (i, x) in enumerate(list(map(int, input().split())))]
	bases = []
	for _ in range(b):
		(d, g) = map(int, input().split())
		bases.append((d, g))
	ships_copy = ships.copy()
	bases.sort()
	ships.sort()
	len_bases = len(bases)
	ans = {}
	i = 0
	acc_g = 0
	for ship in ships:
		while i < len_bases and bases[i][0] <= ship[0]:
			acc_g += bases[i][1]
			i += 1
		ans[ship[1]] = acc_g
	for ship in ships_copy:
		print(ans[ship[1]], end=' ')
	print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


I = input
(s, b) = map(int, I().split())
a = list(map(int, I().split()))
t1 = a.copy()
bases = []
for i in range(b):
	bases.append(list(map(int, I().split())))
bases.sort()
j = 0
a.sort()
d = dict()
s1 = 0
for i in range(s):
	while j < b:
		if bases[j][0] <= a[i]:
			s1 += bases[j][1]
			pass
		else:
			break
		j += 1
	d[a[i]] = s1
for i in t1:
	print(d[i], end=' ')


def bin_search_near(start, end, e):
	mid = (start + end) // 2
	if end < start:
		return end
	if e == base_spec[mid][0]:
		return mid
	if e > base_spec[mid][0]:
		return bin_search_near(mid + 1, end, e)
	if e < base_spec[mid][0]:
		return bin_search_near(start, mid - 1, e)
	return mid
(s, b) = map(int, input().split())
arr = map(int, input().split())
base_spec = []
for i in range(b):
	base_spec.append(list(map(int, input().split())))
base_spec.sort(key=lambda x: x[0])
prev = 0
for i in range(b):
	base_spec[i][1] += prev
	prev = base_spec[i][1]
for i in arr:
	index = bin_search_near(0, b - 1, i)
	if index == -1:
		print(0, end=' ')
		continue
	if base_spec[index][0] > i:
		print(base_spec[index - 1][1], end=' ')
		continue
	print(base_spec[index][1], end=' ')


arr = input()
(N, B) = [int(x) for x in arr.split(' ')]
arr = input()
A = [int(x) for x in arr.split(' ')]
base = []
for i in range(B):
	arr = input()
	(H, G) = [int(x) for x in arr.split(' ')]
	base.append([H, G])
base.sort()
idx = sorted(range(len(A)), key=lambda k: A[k])
A.sort()
s = 0
k = -1
ans = [0] * N
for i in range(N):
	attack = A[i]
	while k < B - 1:
		if base[k + 1][0] <= attack:
			s += base[k + 1][1]
			k += 1
		else:
			break
	ans[idx[i]] = s
for num in ans:
	print(num, end=' ')


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(s, b) = mi()
a = li()
z = [[-1, 0]] + sorted((li() for _ in range(b)))
for i in range(1, b + 1):
	z[i][1] += z[i - 1][1]
v = [p[0] for p in z]
from bisect import bisect_right as ub
ans = [z[ub(v, x) - 1][1] for x in a]
print(*ans)


def solve(bl, i, l, r):
	while l <= r:
		if i < bl[l][0]:
			return 0
		elif i >= bl[r][0]:
			return bl[r][1]
		m = (l + r) // 2
		if m == l:
			return bl[l][1]
		if i >= bl[m][0]:
			l = m
		else:
			r = m - 1
	return 0
(s, b) = [int(i) for i in input().split()]
sl = [int(i) for i in input().split()]
bl = []
for i in range(b):
	bl.append([int(i) for i in input().split()])
bl.sort()
for i in range(1, b):
	bl[i][1] += bl[i - 1][1]
for i in sl:
	print(solve(bl, i, 0, b - 1), end=' ')
print()


from bisect import bisect_right
(s, b) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in range(b):
	(x, y) = map(int, input().split())
	try:
		d[x] += y
	except:
		d[x] = y
p = list(d.keys())
p.sort()
s1 = 0
for i in p:
	s1 += d[i]
	d[i] = s1
for i in a:
	if bisect_right(p, i) != 0:
		u = d[p[bisect_right(p, i) - 1]]
		print(u, end=' ')
	else:
		print(0, end=' ')


from bisect import bisect
(s, b) = [int(p) for p in input().split()]
arr = [int(p) for p in input().split()]
a = []
for i in range(b):
	a.append([int(p) for p in input().split()])
a.sort(key=lambda x: x[0])
gold = [a[0][1]]
d = []
for i in a:
	d.append(i[0])
for i in range(1, b):
	gold.append(gold[-1] + a[i][1])
for i in arr:
	ind = bisect(d, i)
	if ind == 0:
		print(0)
	else:
		print(gold[ind - 1])


sb = input().split()
s = int(sb[0])
b = int(sb[1])
a = list(map(int, input().split()))
bases = []
for _ in range(b):
	dg = list(map(int, input().split()))
	bases.append(dg)
bases.sort(key=lambda a: a[0])
sum_total = 0
for i in bases:
	sum_total += i[1]
	i[1] = sum_total
dg = [*zip(*bases)]
a_sorted = []
a_sorted += a
a_sorted.sort()
g = []
j = 0
for i in a_sorted:
	while j < b:
		if dg[0][j] > i:
			if j > 0:
				g.append(dg[1][j - 1])
			else:
				g.append(0)
			break
		elif j == b - 1:
			g.append(dg[1][j])
			break
		j += 1
for i in a:
	index = a_sorted.index(i)
	print(g[index], end=' ')


from sys import stdin

def binary(A, x):
	N = len(A)
	(low, hi) = (0, N)
	while low + 1 != hi:
		mid = low + (hi - low >> 1)
		if x < A[mid]:
			hi = mid
		else:
			low = mid
	return low

def main():
	(s, b) = stdin.readline().split()
	line = list(map(int, stdin.readline().split()))
	gold = {}
	l = list()
	for _ in range(int(b)):
		(d, g) = map(int, stdin.readline().split())
		if gold.get(d) == None:
			gold[d] = g
			l.append(d)
		else:
			gold[d] += g
	l.sort()
	i = 1
	while i < len(l):
		gold[l[i]] += gold[l[i - 1]]
		i += 1
	s = int(s)
	for i in range(s):
		it = binary(l, line[i])
		if i == s - 1:
			if it == 0 and line[i] < l[it]:
				print(0)
			else:
				print(gold[l[it]])
		elif it == 0 and line[i] < l[it]:
			print(0, end=' ')
		else:
			print(gold[l[it]], end=' ')
main()


import sys
(s, base) = map(int, sys.stdin.readline().strip().split())
power = sys.stdin.readline().strip().split()
power = [int(p) for p in power]
difPower = {}
for p in power:
	difPower[p] = 1
difPower = list(difPower)
difPower.sort()
maxDP = difPower[-1]
bases = {}
for inp in range(base):
	(df, gld) = map(int, sys.stdin.readline().strip().split())
	if df <= maxDP:
		try:
			bases[df] += gld
		except:
			bases[df] = gld
difBases = list(bases)
difBases.sort()
allGold = {}
baseI = 0
powI = 0
while baseI < len(difBases) and powI < len(difPower):
	if difBases[baseI] > difPower[powI]:
		powI += 1
		try:
			allGold[difPower[powI]] = allGold[difPower[powI - 1]]
		except:
			allGold[difPower[powI - 1]] = 0
			allGold[difPower[powI]] = 0
	else:
		try:
			allGold[difPower[powI]] += bases[difBases[baseI]]
		except:
			allGold[difPower[powI]] = bases[difBases[baseI]]
		baseI += 1
powI += 1
while powI < len(difPower):
	try:
		allGold[difPower[powI]] = allGold[difPower[powI - 1]]
	except:
		allGold[difPower[powI - 1]] = 0
		allGold[difPower[powI]] = 0
	powI += 1
for p in power:
	try:
		print(allGold[p], end=' ')
	except:
		print(0, end=' ')


(s, b) = map(int, input().split())
ships = [int(z) for z in input().split()]

def binsearch(nums, target):
	left = 0
	right = len(nums) - 1
	while left <= right:
		mid = (left + right) // 2
		if nums[mid][0] == target:
			return mid
		elif nums[mid][0] > target:
			right = mid - 1
		elif nums[mid][0] < target:
			left = mid + 1
	return left
bases = []
for defense in range(b):
	bases.append([int(z) for z in input().split()])
bases.sort()
prefsums = [bases[0][1]]
for i in range(1, b):
	prefsums.append(prefsums[i - 1] + bases[i][1])
res = []
for i in ships:
	pl = binsearch(bases, i + 0.1)
	if pl == 0:
		res.append(0)
	else:
		res.append(prefsums[pl - 1])
print(*res)