Ordering Pizza

또다시 Start[c]up 결승전이 열렸고, 이는 현장 참가자들을 위해 피자를 주문해야 한다는 뜻이다. 피자는 단 2가지 종류만 있으며(물론 실제로는 그렇지 않지만, 이 문제에서는 그렇다고 가정하자), 모든 피자는 정확히 S개의 조각으로 이루어져 있다.

i-th 참가자는 피자 si조각을 먹으며, 먹는 종류 1 피자 한 조각마다 ai의 행복도를 얻고, 먹는 종류 2 피자 한 조각마다 bi의 행복도를 얻는다고 알려져 있다. 종류 1 피자와 종류 2 피자를 원하는 수만큼 주문할 수 있지만, 모든 참가자가 자신에게 필요한 수의 조각을 먹을 수 있도록 가능한 최소 수의 피자를 사고자 한다. 이 제약하에서 달성할 수 있는 총 행복도의 최댓값은 얼마인가?

입력의 첫째 줄에는 각각 참가자의 수와 피자 한 판당 조각 수를 나타내는 정수 N and S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105)가 주어진다. 이어서 N개의 줄이 주어진다.

그러한 줄 중 i-th 줄에는 정수 si, ai, bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105)가 주어진다. 각각 i-th 참가자가 먹을 조각의 수, 그 참가자가 먹는 종류 1 피자 한 조각마다 얻는 행복도, 그 참가자가 먹는 종류 2 피자 한 조각마다 얻는 행복도를 나타낸다.

달성할 수 있는 총 행복도의 최댓값을 출력한다.

첫 번째 예제에서는 피자를 한 판만 사면 된다. 종류 1 피자를 사면 총 행복도는 3·5 + 4·6 + 5·9 = 84이고, 종류 2 피자를 사면 총 행복도는 3·7 + 4·7 + 5·5 = 74이다.