You have $N$ items that you want to put them into a knapsack. Item $i$ has value $v_i$, weight $w_i$ and limitation $m_i$.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most $W$, that is capacity of the knapsack.
* You can select at most $m_i$ items for $i$-th item.



Find the maximum total value of items in the knapsack.

Constraints

* $1 \le N \le 50$
* $1 \le v_i \le 50$
* $1 \le w_i \le 10^9$
* $1 \le m_i \le 10^9$
* $1 \le W \le 10^9$

Input


$N$ $W$
$v_1$ $w_1$ $m_1$
$v_2$ $w_2$ $m_2$
:
$v_N$ $w_N$ $m_N$


The first line consists of the integers $N$ and $W$. In the following $N$ lines, the value, weight and limitation of the $i$-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 8
4 3 2
2 1 1
1 2 4
3 2 2


Output

12


Input

2 100
1 1 100
2 1 50


Output

150


Input

5 1000000000
3 5 1000000000
7 6 1000000000
4 4 1000000000
6 8 1000000000
2 5 1000000000


Output

1166666666

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
from collections import deque
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
	(N, W) = map(int, readline().split())
	vs = [0] * N
	ws = [0] * N
	ms = [0] * N
	for i in range(N):
		(vs[i], ws[i], ms[i]) = map(int, readline().split())
	V0 = max(vs)
	V = sum((v * min(V0, m) for (v, m) in zip(vs, ms)))
	dp = [W + 1] * (V + 1)
	dp[0] = 0
	for i in range(N):
		v = vs[i]
		w = ws[i]
		m = ms[i]
		c = min(V0, m)
		ms[i] -= c
		for k in range(v):
			que = deque()
			push = que.append
			popf = que.popleft
			popb = que.pop
			for j in range((V - k) // v + 1):
				a = dp[k + j * v] - j * w
				while que and a <= que[-1][1]:
					popb()
				push((j, a))
				(p, b) = que[0]
				dp[k + j * v] = b + j * w
				if que and p <= j - c:
					popf()
	(*I,) = range(N)
	I.sort(key=lambda x: ws[x] / vs[x])
	(*S,) = [(vs[i], ws[i], ms[i]) for i in I]
	ans = 0

	def greedy():
		yield 0
		for i in range(V + 1):
			if dp[i] > W:
				continue
			rest = W - dp[i]
			r = i
			for (v, w, m) in S:
				m = min(m, rest // w)
				r += m * v
				rest -= m * w
			yield r
	write('%d\n' % max(greedy()))
solve()


from heapq import heappush, heappop

def max_value(t, xs):

	def _cost(weight, value, i):
		for j in range(i, n):
			(v, w) = xs[j]
			if weight + w > t:
				return (-value, -value - v / w * (t - weight))
			weight += w
			value += v
		return (-value, -value * 1.0)
	n = len(xs)
	xs.sort(key=lambda x: x[1], reverse=True)
	xs.sort(key=lambda x: x[0] / x[1], reverse=True)
	(u, c) = _cost(0, 0, 0)
	heap = [(c, u, 0, 0, 0)]
	maxcost = u
	while heap:
		(cost, upper, weight, value, i) = heappop(heap)
		if cost > maxcost:
			break
		if i < n:
			(v, w) = xs[i]
			if weight + w <= t:
				heappush(heap, (cost, upper, weight + w, value + v, i + 1))
			(u, c) = _cost(weight, value, i + 1)
			if c < maxcost:
				if u < maxcost:
					maxcost = u
				heappush(heap, (c, u, weight, value, i + 1))
	return -maxcost

def run():
	(n, t) = [int(i) for i in input().split()]
	xs = []
	for _ in range(n):
		(v, w, m) = [int(i) for i in input().split()]
		for i in range(m.bit_length() - 1):
			h = 2 ** i
			m -= h
			xs.append((v * h, w * h))
		if m > 0:
			xs.append((v * m, w * m))
	print(max_value(t, xs))
run()


from typing import Tuple, List
from heapq import heappush, heappop

def max_value(max_weight: int, items: List[Tuple[int, int]]) -> float:

	def _cost(weight: int, value: int, i: int) -> Tuple[int, float]:
		for j in range(i, n):
			(v, w) = items[j]
			if weight + w > max_weight:
				return (-value, -value - v / w * (max_weight - weight))
			weight += w
			value += v
		return (-value, -value * 1.0)
	n = len(items)
	items.sort(key=lambda x: x[1], reverse=True)
	items.sort(key=lambda x: x[0] / x[1], reverse=True)
	(u, c) = _cost(0, 0, 0)
	heap = [(c, u, 0, 0, 0)]
	maxcost = u
	while heap:
		(cost, upper, weight, value, i) = heappop(heap)
		if cost > maxcost:
			break
		if i < n:
			(v, w) = items[i]
			if weight + w <= max_weight:
				heappush(heap, (cost, upper, weight + w, value + v, i + 1))
			(u, c) = _cost(weight, value, i + 1)
			if c < maxcost:
				if u < maxcost:
					maxcost = u
				heappush(heap, (c, u, weight, value, i + 1))
	return -maxcost
(N, W) = map(lambda x: int(x), input().split())
items: List[Tuple[int, int]] = []
for _ in range(N):
	(v, w, m) = map(lambda x: int(x), input().split())
	for i in range(m.bit_length() - 1):
		h = 2 ** i
		m -= h
		items.append((v * h, w * h))
	if m > 0:
		items.append((v * m, w * m))
print(max_value(W, items))


def main():
	from collections import deque
	from functools import cmp_to_key
	(N, W, *A) = map(int, open(0).read().split())
	A = [list(a) for a in zip(*[iter(A)] * 3)]
	Vmax = max((v for (v, w, m) in A))
	Vsum = 0
	B = []
	for (i, (v, w, m)) in enumerate(A):
		m_upper = min(m, Vmax - 1)
		m_rest = m - m_upper
		A[i][2] = m_upper
		if m_rest:
			B.append((v, w, m_rest))
		Vsum += v * m_upper
	INF = 1 << 60
	dp = [INF] * (Vsum + 1)
	dp[0] = 0
	for (v, w, m) in A:
		for ofs in range(v):
			q = deque()
			for j in range(Vsum + 1):
				vj = ofs + j * v
				if vj > Vsum:
					break
				src = dp[vj] - j * w
				while q and q[-1][1] >= src:
					q.pop()
				q.append((j, src))
				if q:
					(ni, nw) = q[0]
					dp[vj] = nw + j * w
					if ni == j - m:
						q.popleft()
	B.sort(key=cmp_to_key(lambda a, b: -1 if a[0] * b[1] > a[1] * b[0] else 1))
	ans = 0
	for (V, d) in enumerate(dp):
		if d > W:
			continue
		W_rest = W - d
		for (v, w, m) in B:
			n_item = min(m, W_rest // w)
			if n_item:
				V += n_item * v
				W_rest -= n_item * w
		if ans < V:
			ans = V
	print(ans)
main()


iim = lambda : map(int, input().rstrip().split())
from heapq import heappush, heappop

def resolve():
	(N, W) = iim()
	S = [list(iim()) for i in range(N)]

	def f1(v, w, m):
		mm = []
		i = 1
		while i <= m:
			yield i
			m -= i
			i <<= 1
		if m:
			yield m
	SS = list(sorted(((v * i, w * i) for (v, w, m) in S for i in f1(v, w, m)), key=lambda x: (x[0] / x[1], x[1]), reverse=True))
	NN = len(SS)

	def ubound(v, w, i):
		for j in range(i, NN):
			(vj, wj) = SS[j]
			if w + wj > W:
				return (-v, -v - (W - w) * vj / wj)
			w += wj
			v += vj
		return (-v, -v)
	(u0, u1) = ubound(0, 0, 0)
	um = u0
	ans = 0
	q = []
	heappush(q, (u1, u0, 0, 0, 0))
	while q:
		(uq0, uq1, vq, wq, i) = heappop(q)
		if uq0 > um:
			break
		if i >= NN:
			continue
		(vi, wi) = SS[i]
		if wq + wi < W:
			heappush(q, (uq0, uq1, vq + vi, wq + wi, i + 1))
		(u0, u1) = ubound(vq, wq, i + 1)
		if u1 <= um:
			if u0 < um:
				um = u0
			heappush(q, (u1, u0, vq, wq, i + 1))
	print(-um)
resolve()