Under construction

Still being built. Things may change

Demo Clean Up

Time limit1sMemory limit1024 MB

Summary
Given a truck capacity and the weights of debris pieces on each input line, find the minimum number of truckloads needed to haul everything away.
Level

Medium6 of 10

Topics
Backtracking, Sorting
Solved
No attempts yet

Problem

A demolition company has hired you to write a program. After every project, they must haul away all the debris, and they want to know how many truck loads it will take. Given the maximum weight the company truck can carry in a single load and the weight of each piece of debris, find the minimum number of truck loads needed to clear the site.

Input

There is an unknown number of inputs, each on its own line. Each input starts with the amount the truck can transport in a single load, followed by the weight of each piece of debris at the site. Values on a line are separated by a single space.

Output

For each input, print the minimum number of loads needed to clear the site. Print each result on its own line.

Examples1

  1. Example 1

    Input
    100 75 75 50
50 25 26 12 12 18
17 2 12 15 16 8 8 8
    Expected output
    3
2
5