Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has recently got a broadband internet connection. His history of internet data usage is provided as below.

During the first T_{1} minutes, the internet data used was D_{1} MBs per minute, and during the next T_{2} minutes, it was D_{2} MBs per minute, and so on till during last T_{N} minutes it was D_{N} MBs per minute.

The internet provider charges the Chef 1 dollar for every 1 MB data used, except for the first K minutes, when the internet data is free as part of the plan provided to Chef.

Please find out the total amount that Chef has to pay the internet provider (in dollars).

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

First line of the input contains a single integer TC the number of test cases. Description of TC test cases follow.
First line of each test case contains two space separated integers N and K.
Next N lines of each test case contains information about the internet data usage. Specifically, in the i-th line, there will be two space separated integers: T_{i} and D_{i}. 

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

For each test case output a single integer in separate line, the amount that Chef has to pay in dollars.

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

$1 ≤ TC ≤ 1,000$
$1 ≤ N ≤ 10$
$0 ≤ K ≤ T_{1} + T_{2} + ... + T_{N} $
$1 ≤ T_{i}, D_{i} ≤ 10$

----- Sample Input 1 ------ 
3

2 2

2 1

2 3

2 2

1 2

2 3

3 0

1 2

2 4

10 10
----- Sample Output 1 ------ 
6

3

110
----- explanation 1 ------ 
Example case 1. For the first two minutes, internet data of usage of Chef is free. He has to pay for last 2 minutes only, for which he will be charged at 3 dollars per minute, i.e. total 6 dollars.

Example case 2. For the first two minutes, internet data of usage of Chef is free. He has to pay for last 1 minute only, for which he is being charged at 3 dollars per minute. So, in total he has to pay 3 dollars.

Example case 3. This time, Chef is not provided any free data usage. He has to pay 
for entire data usage, which comes out to be 1 * 2 + 2 * 4 + 10 * 10 = 110 dollars.

Difficulty: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if k > 0:
			k = k - t
			if k < 0:
				c += -k * d
		else:
			c += t * d
	print(c)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	ans = 0
	for i in range(N):
		(T, D) = map(int, input().split())
		if T < K:
			K -= T
		else:
			ans += (T - K) * D
			K = 0
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	r = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		a = t
		if k > 0:
			t -= k
		if t >= 0:
			r += t * d
		k -= a
	print(r)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	r = v = f = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if f:
			r += t * d
		else:
			v += t
			if v >= k:
				r += (v - k) * d
				f = 1
	print(r)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		x = t
		if k > 0:
			t = t - k
		if t >= 0:
			s += t * d
		k = k - x
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	count_mins = 0
	price = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if count_mins + t <= k:
			count_mins += t
			pass
		elif count_mins <= k:
			price += (count_mins + t - k) * d
			count_mins += t
		else:
			price += t * d
			count_mins += t
	print(price)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	su = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if k > t:
			k -= t
		else:
			t -= k
			k -= k
		if not k:
			su += t * d
	print(su)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	u = 0
	for j in range(a):
		(x, y) = map(int, input().split())
		if c == 0:
			if x == b or b == 0:
				c = 1
				if b == 0:
					u = u + x * y
			elif c == 0:
				b = b - x
				if b < 0:
					z = abs(b)
					u = u + z * y
					c = 1
		else:
			u = u + x * y
	print(u)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	sum = 0
	for j in range(n):
		(t, d) = map(int, input().split())
		if k > 0:
			k = k - t
			if k < 0:
				sum += -k * d
		else:
			sum += t * d
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	usage = []
	rem = k
	bill = 0
	for i in range(n):
		usage.append(tuple(map(int, input().split())))
	for (l, m) in enumerate(usage):
		if m[0] == rem:
			print(sum([i * j for (i, j) in usage[l + 1:]]))
			break
		elif m[0] > rem:
			print(sum([(i[0] - rem) * i[1] if z == 0 else i[0] * i[1] for (z, i) in enumerate(usage[l:])]))
			break
		else:
			rem = max(rem - m[0], 0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if k >= x:
			k = k - x
		else:
			c += (x - k) * y
			k = 0
	print(c)


for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	money = 0
	for i in range(n):
		(t, d) = map(int, input().split(' '))
		if k >= t:
			k = k - t
			continue
		elif k > 0:
			t = t - k
			k = 0
			money += d * t
		else:
			money += d * t
	print(money)


for _ in range(int(input())):
	(N, o) = map(int, input().split())
	cost = 0
	rem = o
	for i in range(N):
		(time, data) = map(int, input().split())
		if rem >= time:
			rem = rem - time
		else:
			left = time - rem
			rem = 0
			cost += data * left
	print(cost)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	charges = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if k > 0:
			k -= t
			if k >= 0:
				continue
			charges = charges + abs(k) * d
		else:
			charges = charges + t * d
	print(charges)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = 0
	t1 = []
	d1 = []
	for i in range(n):
		(t, d) = map(int, input().split())
		if k >= 0:
			k -= t
			if k < 0:
				s += -k * d
		else:
			s += t * d
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	res = 0
	for j in range(n):
		(t, d) = map(int, input().split())
		if k >= t:
			k = k - t
		else:
			res += (t - k) * d
			k = 0
	print(res)


tc = int(input())
for i in range(tc):
	(n, k) = map(int, input().split())
	pro = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		if k > t:
			k = k - t
		else:
			pro = pro + (t - k) * d
			k = 0
	print(pro)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= k:
			k = k - a
		else:
			c = c + b * (a - k)
			k = 0
	print(c)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= k:
			k -= a
		else:
			ans += (a - k) * b
			k = 0
	print(ans)


TC = int(input())
for i in range(TC):
	(N, K) = map(int, input().split())
	p = 0
	for i in range(N):
		(T, D) = map(int, input().split())
		if T < K:
			K -= T
		else:
			p += D * (T - K)
			K = 0
	print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	result = 0
	for _ in range(n):
		(t, d) = map(int, input().split())
		if k > t:
			k = k - t
		else:
			result = result + (t - k) * d
			k = 0
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = []
	y = []
	s = 0
	for _ in range(n):
		(t, d) = map(int, input().split())
		x.append(t)
		y.append(d)
	for i in range(n):
		if k <= 0:
			break
		if k < x[i]:
			x[i] -= k
			k = 0
		else:
			k -= x[i]
			x[i] = 0
	for i in range(n):
		s += x[i] * y[i]
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	prod = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	for i in l:
		if i[0] <= k:
			k = k - i[0]
		elif i[0] > k and k >= 0:
			prod = prod + (i[0] - k) * i[1]
			k = k - i[0]
		elif k < 0:
			prod = prod + i[0] * i[1]
	print(prod)


tt = int(input())
while tt != 0:
	(n, k) = map(int, input().split())
	m = 0
	s = 0
	f = 0
	while n != 0:
		(t, d) = map(int, input().split())
		if f == 1:
			m += t * d
		else:
			s += t
			if s >= k:
				f = 1
				m = (s - k) * d
		n -= 1
	print(m)
	tt -= 1


for tc in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = 0
	tot = 0
	for t1 in range(n):
		(tn, dn) = map(int, input().split(' '))
		t2 = k
		if k > 0:
			k = k - tn
		if t2 >= tn:
			tn = 0
		if k < 0:
			tn = -1 * k
			k = 0
		s = s + tn * dn
	print(s)


test = int(input())
for i in range(test):
	(N, K) = map(int, input().split())
	total = 0
	for i in range(N):
		(T, D) = map(int, input().split())
		if T >= K:
			T = T - K
			K = 0
		else:
			K = K - T
			T = 0
		total = total + T * D
	print(total)


for o in range(int(input())):
	(n, k) = list(map(int, input().split()))
	(time_list, d_speed_list) = ([], [])
	for items in range(n):
		(t, d) = list(map(int, input().split()))
		time_list.append((t, d))
	new_time_list = []
	for (time_values, d) in time_list:
		if k > 0:
			if k >= time_values:
				new_time_list.append((0, d))
				k = k - time_values
			elif k < time_values and k > 0:
				new_time_list.append((time_values - k, d))
				k = k - time_values
		elif k <= 0:
			new_time_list.append((time_values, d))
	total_price = [t * d for (t, d) in new_time_list]
	print(sum(total_price))


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	sum1 = k
	sum1prev = 0
	data = 0
	for i in range(n):
		(ti, di) = map(int, input().split())
		sum1 = sum1 - ti
		if sum1 < 0:
			if sum1prev > 0 and sum1 < 0:
				data = data + abs(di * sum1)
			else:
				data = data + abs(di * (sum1prev - sum1))
		sum1prev = sum1
	print(data)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	c = 0
	for j in range(N):
		(T, D) = map(int, input().split())
		if K > T:
			K -= T
		else:
			c += (T - K) * D
			K = 0
	print(c)


try:
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		data = 0
		for n in range(N):
			(T, D) = map(int, input().split())
			if T < K:
				K -= T
				T = 0
			else:
				T -= K
				K = 0
			data += T * D
		print(data - K)
except:
	pass


n = int(input())
for i in range(n):
	(m, k) = map(int, input().split())
	sum = 0
	for j in range(m):
		(a, b) = map(int, input().split())
		if k >= a:
			k = k - a
		else:
			sum = sum + (a - k) * b
			k = 0
	print(sum)


tc = int(input())
for _ in range(tc):
	(n, k) = [int(x) for x in input().split()]
	cost = 0
	for i in range(n):
		(t, d) = [int(x) for x in input().split()]
		if k > t:
			k = k - t
		else:
			cost = cost + (t - k) * d
			k = 0
	print(cost)


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	cost = 0
	for i in range(a):
		(x, y) = list(map(int, input().split()))
		if b > 0:
			if b > x:
				b -= x
			else:
				cost += (x - b) * y
				b = 0
		else:
			cost += x * y
	print(cost)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	cost = 0
	for i in range(n):
		(ti, da) = list(map(int, input().split()))
		if k > 0:
			if k >= ti:
				k -= ti
			else:
				cost += (ti - k) * da
				k = 0
		else:
			cost += ti * da
	print(cost)


def solution(n, k):
	bill_amount = 0
	for _ in range(n):
		(t, d) = map(int, input().split())
		if k == t:
			k -= t
			t -= k
			continue
		elif k > t:
			k -= t
			t -= k
			continue
		elif k < t:
			t -= k
			k = 0
		bill_amount += t * d
	return bill_amount
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(solution(n, k))


for _ in range(int(input())):
	sum = 0
	(n, k) = map(int, input().split())
	for i in range(n):
		(t, d) = map(int, input().split())
		k = k - t
		if k < 0:
			sum += abs(k) * d
			k = 0
	print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sum = 0
	lt = [0] * n
	ld = [0] * n
	for i in range(n):
		(lt[i], ld[i]) = map(int, input().split())
	for i in range(n):
		if k > 0:
			t = lt[i]
			lt[i] -= k
			k -= t
		if lt[i] > 0:
			sum += lt[i] * ld[i]
	print(sum)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	final = []
	d_value = []
	for j in range(N):
		(T, D) = map(int, input().split())
		for k in range(T):
			final.append(D)
	print(sum(final[K:]))


tc = int(input())
for dummy in range(tc):
	(n, k) = map(int, input().split())
	total = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		k -= t
		if k < 0:
			total += -k * d
			k = 0
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	total = 0
	for i in range(n):
		(t, d) = map(int, input().split())
		while k != 0 and t != 0:
			k -= 1
			t -= 1
		else:
			total += t * d
	print(total)


import math
from itertools import combinations as cb
from itertools import permutations as pr
from collections import defaultdict as df
from collections import deque as dq
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	(ans, x) = (0, 0)
	for i in range(n):
		(t, d) = map(int, input().split())
		if t <= k:
			k -= t
		else:
			t -= k
			k = 0
			ans += t * d
	print(ans)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	cost = []
	sum = 0
	for j in range(N):
		(T, D) = map(int, input().split())
		for k in range(T):
			cost.append(D)
	for l in range(K, len(cost)):
		sum += cost[l]
	print(sum)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	time = []
	data = []
	for j in range(n):
		(t, d) = map(int, input().split())
		if k != 0:
			if k <= t:
				t = t - k
				k = 0
				time.append(t)
				data.append(d)
			elif k > t:
				k = k - t
				t = 0
				time.append(t)
				data.append(d)
		elif k == 0:
			time.append(t)
			data.append(d)
	for k in range(n):
		ans = ans + time[k] * data[k]
	print(ans)