H. 南昌拌粉的绝妙配比
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

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

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

Input

第一行包含四个整数 $$$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$$$)，表示第 $$$i$$$ 种配料的鲜度、辣度和价格。

Output

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

Examples
Input
3 10 1 1
3 3 4
2 4 3
4 4 5
Output
7
Input
2 5 1 2
3 3 4
2 4 10
Output
-1