Problem Description

There is a train consisting of $ N $ cars. Each car has 3 parts, and the speed that car $ k $ can produce is represented by the sum of the powers of its parts $ A, B, C $ with powers $ A_k, B_k, C_k $ respectively.

Each part can have a power between $ 0 $ and $ F $ inclusive.

If the speeds produced by the cars of the train are not in descending order, the train will collapse while moving.

You and Iroha-chan want to modify as few parts as possible to prevent the train from collapsing. The modified parts can only have powers between $ 0 $ and $ F $ inclusive.

For all $ i < j $, ensure that the speed of car $ i $ is greater than or equal to the speed of car $ j $ by finding the minimum number of parts to modify.

Input Format

The input is given from the standard input in the following format:

$ N $ $ F $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ : $ A_N $ $ B_N $ $ C_N $

Output Format

Output the minimum number of parts to modify.

Sample Input and Output

Sample Input #1

3 100
80 100 60
30 50 70
90 10 80

Sample Output #1

1

Sample Input #2

4 100
30 10 40
10 50 90
20 60 50
30 50 80

Sample Output #2

2

Sample Input #3

4 100
0 0 0
0 0 100
100 100 0
100 100 100

Sample Output #3

4

Sample Input #4

10 100
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49

Sample Output #4

0

Sample Input #5

5 10000000000
1701355307 429870732 6220675835
286943432 6531822025 3789827719
2265045229 9897189805 5070400071
8975758188 6810134144 5515765460
7476103030 3953670242 7426723712

Sample Output #5

4

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq F \leq 10^{10}$
• $0 \leq A_k, B_k, C_k \leq F$ (corrected due to incorrect upper limit, correction date: 2019/05/03 19:06)

Partial Points

• If you correctly solve all test cases where $N \leq 3000$, you will be awarded 300 points.

Sample Explanation 1

For example, changing the power of part $ B $ of car $ 2 $ to $ 85 $ results in the total speeds of $ 240, 185, 180 $ for each car, allowing the train to proceed without collapsing.

Sample Explanation 2

For example, changing the power of part $ B $ of car $ 1 $ to $ 90 $ and the power of part $ C $ of car $ 4 $ to $ 10 $ results in the total speeds of $ 170, 150, 130, 90 $ for each car, allowing the train to proceed without collapsing.

Sample Explanation 3

It might be optimal to make the speeds producible by all cars the same.

见题面 Input 部分

见题面 Output 部分