WW3 is near and Gru wants to recruit minions for his team. Gru went to the planet of minions to recruit minions, he saw that there are two villages separated by a river. He cannot recruit minions from both villages because then his team will have internal conflicts. 

Gru is now in a dilemma about which village to recruit as he wants to have the strongest possible team.

You are given coordinates of houses on the planet. Each house has exactly one minion and his power is given. The planet of minion is considered as a 2-D plane and the river is denoted by a straight line ( $y=mx+c$ ). 
$Note:$ None of the houses are situated on the river.

------ Input: ------

First-line will contain $N$, number of houses. 
Second-line will contain two integers, $m$ and $c$ denoting the river.
Next $N$ lines will have exactly 3 integers $X[i], Y[i], P[i]$ denoting the coordinates of houses and the power of minion in that house 

------ Output: ------
Print the maximum power of the team which Gru can recruit.

------ Constraints  ------
$1 ≤ N ≤ 10^{5}$
$-10^{4} ≤ m,c ≤ 10^{4}$
$-10^{4} ≤ X[i], Y[i] ≤ 10^{4}$
$ 1 ≤ P[i] ≤ 10^{4}$

----- Sample Input 1 ------ 
3
1 0
0 5 5
0 6 5
0 -8 20
----- Sample Output 1 ------ 
20

Source: codechef | Difficulty: EASY
Tags: Geometry

Mathematics


Solutions:
n = int(input())
(m, c) = map(int, input().split())
(a, b) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	if m * x + c < y:
		a = a + p
	else:
		b = b + p
print(max(a, b))


n = int(input())
(m, c) = map(int, input().split())
s1 = 0
s2 = 0
for j in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		s1 += p
	elif y < m * x + c:
		s2 += p
if s1 > s2:
	print(s1)
else:
	print(s2)


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


a = int(input())
ikl = str(input())
gb = ikl.split(' ')
fd = int(gb[0])
cons = int(gb[1])
r = 0
l = 0
for bbv in range(0, a):
	gg = str(input())
	vvx = gg.split(' ')
	upo = int(vvx[1]) - fd * int(vvx[0]) - cons
	if upo > 0:
		r += int(vvx[-1])
	else:
		l += int(vvx[-1])
if r > l:
	print(r)
else:
	print(l)


n = int(input())
(m, c) = [int(x) for x in input().split()]
(up, down) = (0, 0)
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if m * x + c < y:
		up += p
	else:
		down += p
print(max([up, down]))


n = int(input())
(m, c) = map(int, input().split())
l = [0, 0]
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		l[0] += p
	else:
		l[1] += p
print(max(l))


try:
	n = int(input())
	for _ in range(n):
		(m, c) = map(int, input().split())
		a = b = 0
		for i in range(n):
			(x, y, p) = list(map(int, input().split()))
			if y - c > m * x:
				a += p
			elif y - c < m * x:
				b += p
		print(max(a, b))
except:
	pass


n = int(input())
(m, c) = map(int, input().split())
above = 0
below = 0
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x > c:
		above += p
	elif y - m * x < c:
		below += p
print(max(above, below))


t = int(input())
(m, c) = map(int, input().split())
(c1, c2) = (0, 0)
for ni in range(t):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		c1 = c1 + p
	else:
		c2 = c2 + p
print(max(c1, c2))


n = int(input())
(m, c) = [int(i) for i in input().split()]
p1 = 0
p2 = 0
for n in range(n):
	(x, y, p) = [int(i) for i in input().split()]
	key = y - m * x - c
	if key > 0:
		p1 += p
	else:
		p2 += p
res = max(p1, p2)
print(res)


n = int(input())
(m, c) = map(int, input().split())
(pos, neg) = ([], [])
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x - c < 0:
		neg.append(p)
	else:
		pos.append(p)
print(max(sum(pos), sum(neg)))


n = int(input())
(m, c) = map(int, input().split())
(c1, c2) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x - c < 0:
		c1 += p
	else:
		c2 += p
print(max(c1, c2))


n = int(input())
(m, c) = list(map(int, input().split(' ')))
lsum = 0
rsum = 0
for i in range(n):
	(x, y, p) = list(map(int, input().split(' ')))
	Line = x * m + c
	if Line > y:
		lsum += p
	else:
		rsum += p
if lsum > rsum:
	print(lsum)
else:
	print(rsum)


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


n = int(input())
(m, c) = map(int, input().split())
v = [0, 0]
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		v[0] += p
	else:
		v[1] += p
print(max(v))


n = int(input())
(m, c) = map(int, input().split())
power1 = []
power2 = []
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		power1.append(p)
	else:
		power2.append(p)
print(max(sum(power1), sum(power2)))


n = int(input())
(m, c) = map(int, input().split(' '))
t1 = 0
t2 = 0
for i in range(n):
	(x, y, p) = map(int, input().split(' '))
	r = y - m * x - c
	if r > 0:
		t1 = t1 + p
	else:
		t2 = t2 + p
if t1 >= t2:
	print(t1)
else:
	print(t2)


a = int(input(''))
e = 0
d = 0
(m, c) = [int(x) for x in input('').split()]
for j in range(a):
	(X, Y, P) = [int(x) for x in input('').split()]
	if Y < m * X + c:
		e = e + P
	else:
		d = d + P
print(max(e, d))


n = int(input())
(m, c) = map(int, input().split())
nt = 0
st = 0
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		nt += p
	else:
		st += p
print(max(nt, st))


import sys
num_houses = int(input())
(m, c) = map(int, input().split())
power_houses_north = 0
power_houses_south = 0
for i in range(num_houses):
	(x, y, power) = map(int, input().split())
	if y > m * x + c:
		power_houses_north += power
	else:
		power_houses_south += power
print(max([power_houses_north, power_houses_south]))


n = int(input())
(m, c) = map(int, input().split())
P1 = 0
P2 = 0
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y - (m * x + c) < 0:
		P1 += p
	else:
		P2 += p
print(max(P1, P2))


t = int(input())
(m, c) = map(int, input().split())
l = u = 0
while t != 0:
	(x, y, p) = map(int, input().split())
	s = m * x + c
	if y > s:
		u += p
	else:
		l += p
	t -= 1
print(max(l, u))


n = int(input())
(m, c) = map(int, input().split())
v1 = 0
v2 = 0
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x > c:
		v1 += p
	else:
		v2 += p
print(max(v1, v2))


a = int(input())
(m, c) = map(int, input().split())
sum1 = 0
sum2 = 0
for i in range(a):
	(x, y, p) = map(int, input().split())
	d = y - m * x - c
	if d > 0:
		sum1 += p
	else:
		sum2 += p
if sum1 > sum2:
	print(sum1)
else:
	print(sum2)


n = int(input())
(m, c) = map(int, input().split())
(v1p, v2p) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		v1p = v1p + p
	else:
		v2p = v2p + p
print(max(v1p, v2p))


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


n = int(input())
(m, c) = map(int, input().split())
e = 0
f = 0
while n > 0:
	(x, y, z) = map(int, input().split())
	if y > m * x + c:
		e = e + z
	else:
		f = f + z
	n = n - 1
print(max(e, f))


n = int(input())
(m, c) = map(int, input().split())
d = []
e = []
f = []
for i in range(n):
	(x, y, p) = map(int, input().split(' '))
	d.append(x)
	e.append(y)
	f.append(p)
a = []
b = []
for i in range(n):
	if m * d[i] + c - e[i] < 0:
		a.append(f[i])
	else:
		b.append(f[i])
print(max(sum(a), sum(b)))


N = int(input())
(m, c) = map(int, input().split())
(upper, lower) = [0] * 2
for _ in range(N):
	(x, y, p) = map(int, input().split())
	if m * x + c > y:
		upper += p
	else:
		lower += p
print(max(upper, lower))


n = input()
(m, c) = input().split()
upper = []
lower = []
for z in range(0, int(n)):
	(x, y, p) = input().split()
	if int(m) * int(x) + int(c) > int(y):
		lower.append(int(p))
	else:
		upper.append(int(p))
usum = 0
lsum = 0
for j in range(0, len(upper)):
	usum = usum + upper[j]
for k in range(0, len(lower)):
	lsum = lsum + lower[k]
print(max(usum, lsum))


n = int(input())
pos = 0
neg = 0
(m, c) = map(int, input().split())
for _ in range(n):
	(x, y, power) = map(int, input().split())
	value = y - m * x - c
	if value > 0:
		pos += power
	else:
		neg += power
print(max(pos, neg))


t = int(input())
(a, b) = map(int, input().split())
r = []
l = []
for x in range(0, t):
	(x, y, z) = map(int, input().split())
	ans = y - a * x - b
	if ans > 0:
		r.append(z)
	else:
		l.append(z)
print(max(sum(r), sum(l)))


vishnesh = int(input())
(m, c) = list(map(int, input().split()))
s1 = 0
s2 = 0
for i in range(vishnesh):
	(x1, y1, z) = list(map(int, input().split()))
	if m * x1 + c - y1 > 0:
		s1 = s1 + z
	else:
		s2 = s2 + z
print(max(s1, s2))


import math
t = int(input())
above = 0
below = 0
(m, c) = map(int, input().split())
for _ in range(t):
	(x, y, p) = map(int, input().split())
	if y < m * x + c:
		below += p
	else:
		above += p
if below >= above:
	print(below)
else:
	print(above)


n = int(input())
(m, c) = [int(i) for i in input().split()]
maxx1 = 0
maxx2 = 0
for i in range(n):
	(x, y, p) = [int(i) for i in input().split()]
	y1 = m * x + c
	if y - y1 > 0:
		maxx1 += p
	else:
		maxx2 += p
print(max(maxx1, maxx2))


tc = int(input())
(m, c) = list(map(int, input().split()))
a1 = 0
b1 = 0
for i in range(0, tc):
	(x, y, p) = list(map(int, input().split()))
	y1 = m * x + c
	if y - y1 > 0:
		a1 += p
	else:
		b1 += p
print(max(a1, b1))


n = int(input())
(m, c) = map(int, input().split())
power1 = 0
power2 = 0
for test in range(n):
	(x, y, p) = map(int, input().split())
	y1 = m * x + c
	if y1 > y:
		power1 += p
	else:
		power2 += p
print(max(power1, power2))


n = int(input())
(m, c) = map(int, input().split())
l1 = []
l2 = []
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y > m * x + c:
		l1 += [p]
	else:
		l2 += [p]
print(max(sum(l1), sum(l2)))


houses = int(input())
(m, c) = map(int, input().split())
first_village = 0
second_village = 0
for x in range(houses):
	(x, y, p) = map(int, input().split())
	river_y = m * x + c
	if river_y > y:
		first_village += p
	else:
		second_village += p
print(max(first_village, second_village))


n = int(input())
(m, c) = map(int, input().split())
(pos, neg) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	equ = y - m * x - c
	if equ > 0:
		pos += p
	else:
		neg += p
if pos > neg:
	print(pos)
else:
	print(neg)


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


n = int(input())
(m, c) = map(int, input().split())
(s1, s2) = (0, 0)
for _ in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x - c > 0:
		s1 += p
	else:
		s2 += p
print(max(s2, s1))


t = int(input())
(m, c) = map(int, input().split())
a = 0
b = 0
for j in range(t):
	(x, y, p) = map(int, input().split())
	d = y - m * x - c
	if d > 0:
		a += p
	else:
		b += p
if a > b:
	print(a)
else:
	print(b)


n = int(input())
(m, c) = map(int, input().split())
(upPow, lowPow) = (0, 0)
for jj in range(n):
	(x, y, power) = map(int, input().split())
	y1 = m * x + c
	if y < y1:
		lowPow += power
	else:
		upPow += power
print(max(lowPow, upPow))


n = int(input())
(m, c) = map(int, input().split())
sum1 = 0
sum2 = 0
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y - m * x - c > 0:
		sum1 = sum1 + p
	else:
		sum2 = sum2 + p
print(max(sum1, sum2))


(c1, c2) = (0, 0)
n = int(input())
(a, b) = map(int, input().split())
for _ in range(n):
	(x1, y1, p1) = map(int, input().split())
	if y1 - a * x1 - b > 0:
		c1 += p1
	else:
		c2 += p1
print(max(c1, c2))


try:
	n = int(input())
	(m, c) = input().split()
	m = int(m)
	c = int(c)
	x = list()
	y = list()
	p = list()
	v1 = v2 = 0
	aa = bb = cc = ''
	for i in range(n):
		ey = 0
		(aa, bb, cc) = input().split()
		x.append(int(aa))
		y.append(int(bb))
		p.append(int(cc))
		ey = m * x[i] + c
		if ey > y[i]:
			v1 += p[i]
		elif ey < y[i]:
			v2 += p[i]
		else:
			continue
	print(max(v1, v2))
except EOFError as e:
	pass


from collections import defaultdict

def river(x, y, m, c):
	river_y = m * x + c
	return 1 if river_y > y else 0

def solve(n, m, c, villagers):
	sorted_villagers = defaultdict(int)
	for v in villagers:
		sorted_villagers[river(v[0], v[1], m, c)] += v[2]
	return max(sorted_villagers[0], sorted_villagers[1])

def do_codechef():
	n = int(input())
	(m, c) = map(int, input().split(' '))
	villagers = list()
	for _ in range(n):
		(x, y, p) = map(int, input().split(' '))
		villagers.append([x, y, p])
	print(solve(n, m, c, villagers))
do_codechef()
exit()


t = int(input())
count1 = 0
count2 = 0
(n, m) = map(int, input().split())
for _ in range(t):
	(x, y, z) = map(int, input().split())
	if y - x * n - m > 0:
		count1 += z
	else:
		count2 += z
print(max(count1, count2))


n = int(input())
(m, c) = map(int, input().split())
(p1, p2) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	if y < m * x + c:
		p1 += p
	elif y > m * x + c:
		p2 += p
print(max(p1, p2))


n = int(input())
(m, c) = map(int, input().split())
(po, ne) = (0, 0)
for i in range(n):
	(x, y, p) = map(int, input().split())
	k = y - m * x - c
	if k < 0:
		ne += p
	else:
		po += p
print(max(po, ne))


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


n = int(input())
b = 0
d = 0
(m, g) = map(int, input().split(' '))
for i in range(n):
	(x, y, p) = map(int, input().split(' '))
	k = y - m * x - g
	if k > 0:
		b += p
	else:
		d += p
print(max(b, d))