#K34342. Maximizing Successful Dishes

    ID: 25288 Type: Default 1000ms 256MiB

Maximizing Successful Dishes

Maximizing Successful Dishes

You are given N ingredients each with a spiciness level given in the list S. Your task is to determine the maximum number of successful dishes that can be made. A dish is considered successful if the combined spiciness of the ingredients used in that dish is at least T.

Once the accumulated spiciness reaches or exceeds T, the count of successful dishes is incremented and the spiciness accumulator is reset to form the next dish.

Formally, given integers (N) and (T) and a list of integers (S_1, S_2, \ldots, S_N), you must compute the maximum number (k) such that you can partition some or all of the list into (k) (possibly non-contiguous) segments, each with a sum at least (T). Note that the order is determined by first sorting the ingredients in descending order, ensuring that the spicier ingredients are used first for maximum benefit.

inputFormat

The first line of input contains two space-separated integers \(N\) and \(T\), where \(N\) is the number of ingredients and \(T\) is the minimum spiciness required for a dish to be successful.

The second line contains \(N\) space-separated integers representing the spiciness levels of the ingredients.

outputFormat

Output a single integer representing the maximum number of successful dishes that can be made.

## sample
7 100
20 30 40 50 60 70 80
2

</p>