题目描述

译自 ROI Regional 2023 Day2 T1. Неисправный марсоход

“Megabur 2022” 钻机用于在 Byteburg 铺设地铁隧道，它有 ( n ) 个发动机。钻机的供电方式是所有发动机都接收相同的整数电压 ( x )。

每个发动机有两种工作模式，当电压 ( x ) 施加到第 ( i ) 个发动机时，如果 $( x \leq z_i )$，它在第一模式下工作；如果 $( x > z_i )$，它在第二模式下工作。

第 ( i ) 个发动机在第一模式下的单位功率为 $( a_i )$，在第二模式下的单位功率为 $( b_i )$。这意味着，当发动机在第一模式下时，电压每增加 $( 1 )$，其功率增加 $( a_i )$；在第二模式下，功率增加 $( b_i )$。换句话说，当电压为 ( x ) 时，如果第 ( i ) 个发动机在第一模式下工作，其功率为 $( a_i \times x )$；如果在第二模式下工作，其功率为 $( a_i \times z_i + b_i \times (x - z_i) )$。

为了铺设隧道，发动机的总功率必须不小于 $( p )$。需要施加的最小整数电压是多少，才能使发动机的总功率大于或等于 ( p )？

输入格式

第一行输入包含两个整数 ( n ) 和 ( p )（$( 1 \leq n \leq 100 )$，$( 1 \leq p \leq 10^{12} )$）。

接下来的 ( n ) 行描述发动机，每行包含三个整数 $( z_i )$、$( a_i )$、$( b_i )$（$( 1 \leq z_i \leq 10^9 )$，$( 1 \leq a_i, b_i \leq 10^4 )$）。

输出格式

输出一个整数，表示需要施加的最小电压。

样例 1

输入：

1 6
4 1 2

输出：

5

样例 2

输入：

3 15
2 3 3
4 2 1
5 2 2

输出：

3

数据范围与提示

详细子任务附加限制及分值如下表所示：