题目描述

南昌拌粉是当地早餐的灵魂，而一碗正宗拌粉的关键在于配料的搭配。老字号“万方”拌粉有一份祖传秘方：一碗拌粉的总鲜度与总辣度必须恰好等于 $A:B$，只有这样才能激发出最绝妙的口感。

现在店里有 $n$ 种配料可供选择，第 $i$ 种配料的鲜度为 $U_i$，辣度为 $D_i$。价格为 $C_i$。每种配料最多只能加一份。

你带了 $M$ 块钱，想要选择至少一种配料加入拌粉中。你需要满足以下条件：

• 所选配料总价格不超过 $M$；
• 所选配料的总鲜度与总辣度比值恰好为 $A:B$。

在所有满足条件的方案中，你希望拌粉的总鲜度尽可能大。求这个最大总鲜度。无论如何都无法配出绝妙比例，输出 -1。

输入格式

第一行包含四个整数 $n$,$m$,$A$,$B$$(1\le n \le 26,1\le M \le 10^{9},1\le A,B \le 10^4)$，分别表示配料的种类数、你的预算以及目标比例的两个分量。

接下来 $n$ 行，每行包含三个整数 $U_i,D_i,C_i(1\le U_i,D_i,C_i \le 10^9)$。

输出格式

输出一个整数，表示满足条件下最大总鲜度。如果无法满足条件，输出 -1。

3 10 1 1
3 3 4
2 4 3
4 4 5

7

2 5 1 2
3 3 4
2 4 10

-1