Magic Tower

Mo Mo is obsessed with a role‐playing game called "Magic Tower". In this game the player controls a warrior who must traverse the tower, defeat monsters, and eventually rescue the princess trapped at the top.

The warrior’s capabilities are defined by three positive integer attributes: health, attack, and defense. Each monster is similarly defined. When the warrior and a monster engage in battle, they face each other and attack simultaneously once per second. In each round:

• If the warrior’s attack exceeds the monster’s defense, the monster loses \(\text{attack}_W-\text{defense}_M\) health; otherwise, the monster takes no damage.
• If the monster’s attack exceeds the warrior’s defense, the warrior loses \(\text{attack}_M-\text{defense}_W\) health; otherwise, the warrior takes no damage.

The battle lasts for \(r\) seconds, where

[ r = \left\lceil \frac{\text{hp}_M}{\max(\text{attack}_W-\text{defense}_M,,0)} \right\rceil, ]

and the damage the warrior suffers from that monster is \(r \times \max(\text{attack}_M-\text{defense}_W,\,0)\). Note that since both sides attack simultaneously, it is possible that at the end of the battle both the warrior and the monster have health \(\le 0\). The warrior is said to win the fight only if the battle ends in a finite number of rounds and his remaining health is strictly greater than zero.

Before entering the Magic Tower, Mo Mo may purchase the warrior’s initial attributes with coins: each point of health costs 1 coin, each point of attack costs \(C_A\) coins, and each point of defense costs \(C_D\) coins. Since the outcome of a battle between the warrior and any given monster is deterministic once the attributes are fixed, Mo Mo can also choose the order in which to fight the \(n\) monsters.

Your task is to help Mo Mo decide on the initial attributes and the order of battles that minimizes the total coin expenditure required for the warrior to defeat all monsters and rescue the princess.

inputFormat

The first line contains three integers (n), (C_A), and (C_D) (with (1 \le n \le 200)). Each of the next (n) lines contains three positive integers (h_i), (a_i), and (d_i) representing the health, attack, and defense of the i-th monster, respectively.

outputFormat

Output a single integer — the minimum number of coins needed to set the warrior’s attributes so that he can defeat all monsters in some order.

sample

1 2 1
10 10 5

23