지하철 공사

바이트스버그에서 지하철 터널을 파는 데 쓰는 굴착기 「Мегабур 2022」에는 엔진이 $n$개 있다. 모든 엔진에는 같은 정수 전압 $x$가 공급된다.

각 엔진에는 두 가지 모드가 있다. 전압 $x$가 공급될 때 $i$번째 엔진은 $x \le z_i$이면 첫 번째 모드로, $x > z_i$이면 두 번째 모드로 동작한다.

$i$번째 엔진은 첫 번째 모드의 단위 출력 $a_i$와 두 번째 모드의 단위 출력 $b_i$로 특징지어진다. 첫 번째 모드에서는 전압이 1 올라갈 때마다 출력이 $a_i$만큼 늘고, 두 번째 모드에서는 $b_i$만큼 늘어난다. 따라서 전압 $x$에서 $i$번째 엔진의 출력은 첫 번째 모드에서 $a_i x$, 두 번째 모드에서 $a_i z_i + b_i(x - z_i)$이다.

터널을 파려면 엔진들의 총 출력이 $p$ 이상이어야 한다. 총 출력이 $p$ 이상이 되게 하는 최소 정수 전압을 구하라.

첫 줄에 정수 $n$과 $p$가 주어진다 ($1 \le n \le 100$, $1 \le p \le 10^{12}$).

이어지는 $n$개 줄에는 정수 $z_i$, $a_i$, $b_i$가 세 개씩 주어진다 ($1 \le z_i \le 10^9$, $1 \le a_i, b_i \le 10^4$).

총 출력이 $p$ 이상이 되는 최소 전압을 정수 하나로 출력한다.