곤충 미끼

소피는 곤충 미끼를 만드는 회사에서 일한다. 각 미끼는 유인제, 먹이, 독이라는 세 가지 재료로 만들어진다. $n$가지 곤충 종류마다 이를 없애는 재료 조합이 정확히 하나씩 있다. 재료에는 번호가 매겨져 있다.

소피는 새로운 곤충 미끼를 설계하고 있다. 이 미끼가 모든 곤충을 죽일 필요는 없다. 목표는 회사의 이익을 최대화하는 것이다.

생산 비용은 미끼에 포함된 서로 다른 유인제, 먹이, 독의 단가를 모두 더한 값이다. 유인제의 단가는 모두 같고, 먹이와 독도 마찬가지다.

가격은 미끼가 죽일 수 있는 곤충 종류 수에 $p$를 곱한 값이다. 여기서 $p$는 벌레당 효율 계수다. 미끼 한 단위의 이익은 가격에서 생산 비용을 뺀 값이다.

소피가 가장 이익이 큰 미끼를 설계하도록 도와 달라. 곤충 종류 수, 효율 계수, 각 재료의 단가를 입력받아 미끼 한 단위당 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하라.

첫 줄에 정수 $n$, $p$, $c_a$, $c_k$, $c_t$ ($1 \le n, p, c_a, c_k, c_t \le 1000$)가 공백으로 구분되어 주어진다. 각각 곤충 종류 수, 벌레당 효율 계수, 유인제, 먹이, 독의 단가이다.

이어지는 $n$개의 줄에는 세 정수 $a_i$, $k_i$, $t_i$ ($0 \le a_i, k_i, t_i < 256$)가 공백으로 구분되어 주어진다. $i$번째 곤충은 유인제 $a_i$, 먹이 $k_i$, 독 $t_i$를 조합하면 없앨 수 있다. 모든 세쌍 $(a_i, k_i, t_i)$는 서로 다르다.

미끼 한 단위당 얻을 수 있는 최대 이익을 정수 하나로 출력한다.

이 미끼는 유인제 127과 255(비용 $2 \cdot 3 = 6$), 먹이 127(비용 $1 \cdot 10 = 10$), 독 0과 127(비용 $2 \cdot 1 = 2$)을 사용하여 총 생산 비용이 18이다. 1, 3, 4번 곤충을 죽이므로 가격은 30이다. 따라서 미끼 한 단위의 이익은 12이다.