Insects

Sophie works at a company that produces insect baits. Each bait has three ingredients: an attractor, a feed, and a poison. For each of the $n$ insect types, there is exactly one triplet of ingredients that eliminates it. The ingredients are numbered.

Sophie is designing a new insect bait. The bait does not need to kill all the insects. Its goal is to maximize the company's profit.

The production cost is the sum of the unit costs of the distinct attractors, feeds, and poisons the bait contains. All attractors share one unit cost, and the same holds for feeds and poisons.

The price is the number of insect types the bait can kill, multiplied by $p$, the bang-per-bug factor. The profit per unit of bait is its price minus its production cost.

Help Sophie design the most profitable bait. Write a program that reads the insect count, the bang-per-bug factor, and the unit costs, then determines the maximum possible profit per unit of bait.

The first line contains the integers $n$, $p$, $c_a$, $c_k$, and $c_t$ ($1 \le n, p, c_a, c_k, c_t \le 1000$), separated by single spaces. They are the number of insect types, the bang-per-bug factor, and the unit costs of attractors, feeds, and poisons, respectively.

Each of the next $n$ lines contains three integers $a_i$, $k_i$, and $t_i$ ($0 \le a_i, k_i, t_i < 256$), separated by single spaces. The $i$-th insect can be eliminated by combining attractor $a_i$, feed $k_i$, and poison $t_i$. All triplets $(a_i, k_i, t_i)$ are pairwise different.

Print a single integer: the maximum possible profit per unit of bait.

The bait uses attractors 127 and 255 (cost $2 \cdot 3 = 6$), feed 127 (cost $1 \cdot 10 = 10$), and poisons 0 and 127 (cost $2 \cdot 1 = 2$), for a total production cost of 18. It kills insect types 1, 3, and 4, so its price is 30. The profit per unit is therefore 12.