#P1028. [2026 CCPC_NC_I H] 南昌拌粉的绝妙配比

[2026 CCPC_NC_I H] 南昌拌粉的绝妙配比

Description

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

现在店里有 nn 种配料可供选择,第 ii 种配料的鲜度为 UiU_i,辣度为 DiD_i,价格为 CiC_i。每种配料最多只能加一份。

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

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

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

Format

Input

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

接下来 nn 行,每行包含三个整数 Ui,Di,CiU_i,D_i,C_i (1≤Ui,Di,Ci≤1091\le U_i,D_i,C_i\le 10^9),表示第 ii 种配料的鲜度、辣度和价格。

Output

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

Samples

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