Movie Scheduling with Time Slots

You are given n movies with corresponding durations and a single time slot duration m. Your task is to assign each movie to a time slot such that the total duration of movies in a time slot does not exceed m minutes. Determine the minimum number of time slots required to schedule all the movies, or output -1 if at least one movie cannot fit in any slot because its duration exceeds m.

Note: Each input movie must be scheduled entirely within one slot, and the order of movies can be rearranged arbitrarily.

The problem can be modeled as a bin packing problem. In mathematical terms, given a list of durations \(d_1, d_2, \ldots, d_n\) and a slot capacity \(m\), we want to partition the list into subsets \(S_1, S_2, \ldots, S_k\) such that for every subset \(S_i\), \[ \sum_{d \in S_i} d \le m, \] and k is minimized. If any \(d_i > m\), then the answer is -1.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains two space-separated integers: n (the number of movies) and m (the maximum allowed duration per time slot).
2. The second line contains n space-separated integers representing the durations of the movies.

It is guaranteed that n ≥ 1 and all durations are positive integers.

outputFormat

Output the minimum number of time slots required to schedule all the movies on a single line to stdout. If it is impossible because at least one movie duration exceeds m, output -1.

5 120
90 30 40 50 60

3