Read problems statements in Mandarin Chinese and Russian as well. 

You are given a transparent three-dimensional table, the height equals to H and the base is a two-dimensional table N∙M.
The layers of the 3D table are numbered from 1 to H. Each layer is a two-dimensional table, the rows are numbered from 1 to N and the columns are numbered from 1 to M. A pair (i, j) (1 ≤ i ≤ N, 1 ≤ j ≤ M) corresponds to the cell at the intersection of i'th row and j'th column of a two-dimensional table.
We can paint cells of the three-dimensional table, but not more than T_{k} cells on k'th layer can be painted. Painting of one cell on k'th layer costs C_{k}. Your task is to find the minimum cost of painting the table thus that it can't be seen throught from the top (there is no cell which is unpainted on every layer). Formally you need to find a painting, that for any pair (i, j) (1 ≤ i ≤ N, 1 ≤ j ≤ M) there is a layer k (1 ≤ k ≤ H), where cell (i, j) is painted. If there is no such a painting then the answer is "Impossible". 

------ Input ------ 

The first line contains three integers N, M and H.
Each of the next H lines contains two integers T_{k} and C_{k}.

------ Output ------ 

The output should contain the minimum cost of the painting if there is one, otherwise output Impossible without quotes.

------ Constraints ------ 

1 ≤ N∙M ≤ 10^{12};
1 ≤ H ≤ 100000;
0 ≤ T_{k} ≤ 10^{12}, for each layer;
0 ≤ C_{k} ≤ 10^{5}, for each layer.

----- Sample Input 1 ------ 
3 4 2
6 1
6 2
----- Sample Output 1 ------ 
18
----- explanation 1 ------ 
In the first example, we should paint 6 cells on the first layer and 6 cells on the second layer.

----- Sample Input 2 ------ 
2 2 3
1 1
1 2
1 3
----- Sample Output 2 ------ 
Impossible
----- explanation 2 ------ 
In the second example, there are not enough cells to paint the table properly.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
def main():
	(n, m, h) = map(int, input().split(' '))
	layers = []
	for i in range(h):
		layers.append(list(map(int, input().split(' '))))
	cellsRem = n * m
	cost = 0
	for i in sorted(list(layers), key=lambda x: x[1]):
		if cellsRem > i[0]:
			cost += i[0] * i[1]
			cellsRem -= i[0]
		else:
			cost += cellsRem * i[1]
			cellsRem = 0
			break
	if cellsRem > 0:
		print('Impossible')
	else:
		print(cost)
main()


(n, m, h) = map(int, input().split())
cells_to_be_painted = 0
a = []
for i in range(h):
	(t, c) = map(int, input().split())
	cells_to_be_painted += t
	a.append([c, t])
if cells_to_be_painted < m * n:
	print('Impossible')
elif cells_to_be_painted == m * n:
	cost = 0
	for i in range(h):
		cost += a[i][0] * a[i][1]
	print(cost)
else:
	a.sort()
	cost = 0
	cells_not_painted = m * n
	k = 0
	while cells_not_painted != 0:
		v = min(cells_not_painted, a[k][1])
		cost += v * a[k][0]
		k += 1
		cells_not_painted -= v
	print(cost)


def solve():
	(n, m, h) = map(int, input().split())
	Tcells = 0
	d = []
	for _ in range(h):
		(t, c) = map(int, input().split())
		d.append([t, c])
		Tcells += t
	d_sorted = sorted(d, key=lambda x: x[1])
	Pcells = 0
	cost = 0
	k = m * n
	if k <= Tcells:
		for i in d_sorted:
			Pcells += i[0]
			if Pcells < k:
				cost += i[0] * i[1]
			else:
				cost += (k - Pcells + i[0]) * i[1]
				print(cost)
				break
	else:
		print('Impossible')
solve()


import sys
[n, m, h] = list(map(int, input().split()))
cnt = 0
cost = []
for i in range(h):
	[t, c] = list(map(int, input().split()))
	cost.append([c, t])
cost.sort()
ans = 0
for i in range(h):
	cnt += cost[i][1]
	ans += cost[i][0] * cost[i][1]
	if cnt == n * m:
		print(ans)
		sys.exit(0)
	elif cnt > n * m:
		x = cnt - n * m
		c = cost[i][0]
		ans = ans - c * x
		print(ans)
		sys.exit(0)
print('Impossible')


s = input().split(' ')
(n, m, h) = (int(s[0]), int(s[1]), int(s[2]))
numCells = n * m
cost = []
cellsPainted = []
for _ in range(h):
	s = input().split(' ')
	(t, c) = (int(s[0]), int(s[1]))
	cost.append((c, t))
	cellsPainted.append(t)
if sum(cellsPainted) < numCells:
	print('Impossible')
else:
	cost = sorted(cost, key=lambda x: x[0])
	curCost = 0
	i = 0
	while numCells > 0:
		curCost += cost[i][0] * min(cost[i][1], numCells)
		numCells -= cost[i][1]
		i += 1
	print(curCost)


(N, M, H) = map(int, input().split())
left = N * M
array = []
for i in range(H):
	(t, c) = map(int, input().split())
	array.append([c, t])
array.sort()
cost = 0
for i in range(H):
	p = array[i]
	if left <= p[1]:
		cost += left * p[0]
		left = 0
		break
	else:
		cost += p[0] * p[1]
		left -= p[1]
if left == 0:
	print(cost)
else:
	print('Impossible')


line = input()
p = line.split()
n = int(p[0])
m = int(p[1])
t = int(p[2])
ar = list()
for _ in range(t):
	line = input()
	p = line.split()
	x = int(p[0])
	y = int(p[1])
	ar.append((y, x))
ar = sorted(ar)
c = 0
cou = 0
area = m * n
for (y, x) in ar:
	r = area - cou
	if x < r:
		cou = cou + x
		c = c + x * y
	else:
		cou = cou + r
		c = c + y * r
		break
if cou != area:
	print('Impossible')
else:
	print(c)


(n, m, h) = [int(x) for x in input().split()]
k = []
for i in range(h):
	k += [[int(x) for x in input().split()]]
k = sorted(k, key=lambda x: x[1])
total = n * m
c = 0
for i in k:
	if total > 0:
		d = min(total, i[0])
		c += d * i[1]
		total -= d
	else:
		break
if total > 0:
	print('Impossible')
else:
	print(c)


(n, m, h) = map(int, input().split())
base = n * m
paint_available = 0
paint_value = []
for z in range(h):
	(t, c) = map(int, input().split())
	paint_available += t
	paint_value.append([c, t])
if paint_available < base:
	print('Impossible')
else:
	paint_value.sort(key=lambda x: x[0])
	cost = 0
	for i in range(h):
		if base > paint_value[i][1]:
			base -= paint_value[i][1]
			value = paint_value[i][0] * paint_value[i][1]
			cost += value
		else:
			value = base * paint_value[i][0]
			cost += value
			base = 0
			break
	print(cost)


(n, m, h) = map(int, input().split())
numCells = n * m
tk_ck = []
tot = 0
for _ in range(h):
	(t, c) = map(int, input().split())
	tk_ck.append((t, c))
	tot += t
if tot < numCells:
	print('Impossible')
else:
	tk_ck = sorted(tk_ck, key=lambda x: x[1])
	curCost = 0
	i = 0
	while numCells > 0:
		curCost += tk_ck[i][1] * min(tk_ck[i][0], numCells)
		numCells -= tk_ck[i][0]
		i += 1
	print(curCost)


(n, m, h) = list(map(int, input().split()))
temp = []
tot = 0
for i in range(h):
	(v1, v2) = list(map(int, input().split()))
	tot += v1
	temp.append((v2, v1))
if tot < m * n:
	print('Impossible')
else:
	temp.sort(key=lambda x: x[0])
	ans = 0
	topaint = n * m
	for i in range(h):
		if topaint == 0:
			break
		canpaint = min(temp[i][1], topaint)
		ans += canpaint * temp[i][0]
		topaint -= canpaint
	print(ans)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(N, M, H, layers):
	total_to_paint = N * M
	layers.sort(key=operator.itemgetter(1))
	cost = 0
	for l in layers:
		if total_to_paint <= l[0]:
			cost += total_to_paint * l[1]
			total_to_paint = 0
			break
		else:
			cost += l[1] * l[0]
			total_to_paint -= l[0]
	return cost if total_to_paint == 0 else 'Impossible'

def main():
	data = sys.stdin
	(N, M, H) = list(map(int, data.readline().split()))
	layers = []
	for h in range(H):
		layers.append(list(map(int, data.readline().split())))
	res = alg(N, M, H, layers)
	print(res)
main()


(n, m, h) = input().strip().split()
n = int(n)
m = int(m)
h = int(h)
p = []
add = 0
for i in range(0, h):
	a = list(map(int, input().strip().split()))
	add += a[0]
	p.append(a)
if add < m * n:
	print('Impossible')
else:
	p = sorted(p, key=lambda x: x[1])
	total = n * m
	cost = 0
	for j in p:
		if j[0] <= total:
			cost += j[0] * j[1]
			total -= j[0]
		elif j[0] > total:
			cost += total * j[1]
			total = 0
			break
	print(cost)


try:
	(n, m, h) = map(int, input().split())
	T = n * m
	D = dict()
	Sk = 0
	for _ in range(h):
		(tk, ck) = map(int, input().split())
		D[ck] = D.get(ck, 0) + tk
		Sk += tk
	if Sk < T:
		print('Impossible')
	else:
		res = 0
		cl = list(D.keys())
		cl.sort()
		for ck in cl:
			if D[ck] <= T:
				res += ck * D[ck]
				T -= D[ck]
			else:
				res += ck * T
				break
		print(res)
except Exception as err:
	print('error occured!!', err)
	pass


stri = input().split()
(n, m, h) = (int(stri[0]), int(stri[1]), int(stri[2]))
tvalues = []
for i in range(h):
	stri = input().split()
	tvalues.append((int(stri[0]), int(stri[1])))
tvalues.sort(key=lambda x: x[1])
count = 0
answer = 0
total = n * m
i = 0
while count < total and i <= h - 1:
	if tvalues[i][0] <= total - count:
		answer += tvalues[i][1] * tvalues[i][0]
		count += tvalues[i][0]
		i += 1
	else:
		remaining = total - count
		count += remaining
		answer += tvalues[i][1] * remaining
if count < total:
	print('Impossible')
else:
	print(answer)


(n, m, h) = [int(word) for word in input().split()]
ct_vals = []
for k in range(h):
	(t, c) = [int(word) for word in input().split()]
	ct_vals.append((c, t))
ct_vals = sorted(ct_vals)
rem_cells = m * n
cost = 0
for k in range(h):
	if rem_cells > ct_vals[k][1]:
		rem_cells -= ct_vals[k][1]
		cost += ct_vals[k][0] * ct_vals[k][1]
	else:
		cost += ct_vals[k][0] * rem_cells
		rem_cells = 0
		break
if rem_cells > 0:
	print('Impossible')
else:
	print(cost)


temp = list(map(int, input().split()))
n = temp[0]
m = temp[1]
h = temp[2]
a = []
for t in range(h):
	temp = list(map(int, input().split()))
	a.append([temp[1], temp[0]])
a.sort()
rem = n * m
i = 0
ans = 0
while i < h and rem > 0:
	if a[i][1] <= rem:
		rem -= a[i][1]
		ans += a[i][1] * a[i][0]
	elif a[i][1] > rem:
		ans += rem * a[i][0]
		rem = 0
	i += 1
if rem <= 0:
	print(ans)
else:
	print('Impossible')