AT_past202306_j 忍者

A ninja will fight against $ N $ monsters one by one in order. The attack power of the $ i $ -th monster is $ a_i $ , and its health is $ b_i $ . A monster is immediately defeated when its health becomes $ 0 $ or less. Each monster is either on the ground or flying. If $ x_i = 0 $ , the $ i $ -th monster is on the ground, and if $ x_i = 1 $ , it is flying. The ninja initially has $ M $ shurikens. Each shuriken can be used only once by throwing it. The ninja and the $ i $ -th monster fight as follows: - First, the ninja chooses zero or more shurikens from the ones he has and throws them at the monster. The monster's health decreases by the number of shurikens thrown, and if one or more shurikens are thrown at a flying monster, it lands on the ground. - Then, the ninja and the monster take turns attacking each other. Each attack by the ninja decreases the monster's health by $ 1 $ , and each attack by the monster decreases the ninja's health by $ a_i $ . Here, if the monster is on the ground, the ninja attacks first, and if it is flying, the monster attacks first. Find the minimum possible difference between the ninja's initial health and his health after defeating all the monsters. Assume that the ninja's health is sufficiently large.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ a_1 $ $ b_1 $ $ x_1 $ $ a_2 $ $ b_2 $ $ x_2 $ $ \vdots $ $ a_N $ $ b_N $ $ x_N $

Print the answer.

### Sample Explanation 1 If the ninja fights as follows, his health will decrease by a total of $ 4 $ , which is optimal: - Do not throw any shurikens at the first monster. - Since the monster is flying, it attacks the ninja first. The ninja's health decreases by $ 2 $ . - The ninja attacks. The monster's health becomes $ 1 $ . - The monster attacks. The ninja's health decreases by $ 2 $ . - The ninja attacks. The monster's health becomes $ 0 $ , and it is defeated. - Throw one shuriken at the second monster. The monster's health becomes $ 1 $ . - Since the monster is on the ground, the ninja attacks first. The monster's health becomes $ 0 $ , and it is defeated. ### Sample Explanation 2 If the ninja fights as follows, his health will decrease by a total of $ 1 $ , which is optimal: - Throw two shurikens at the first monster. The monster's health becomes $ 2 $ , and it lands on the ground. - Since the monster is on the ground, the ninja attacks first. The monster's health becomes $ 1 $ . - The monster attacks. The ninja's health decreases by $ 1 $ . - The ninja attacks. The monster's health becomes $ 0 $ , and it is defeated. ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 0 \leq M \leq 10^{11} $ - $ 1 \leq a_i, b_i \leq 3 \times 10^5 $ - $ x_i = 0 $ or $ x_i = 1 $ . - All input values are integers.