Minimum Height Storage

You are given a fixed storage area of width \(W\) and \(N\) boxes. Each box is described by its width and height. The boxes can be arranged in rows (layers) where each layer can contain one or more boxes placed side by side, but the sum of their widths cannot exceed \(W\). The height of a layer is determined by the tallest box in that layer.

The goal is to arrange the boxes to minimize the total stacked height. In this problem, boxes are first sorted in descending order of their heights. Then, starting from the tallest box, each box is added into the current layer if the total width does not exceed \(W\). If a box cannot be placed in the current layer, a new layer is started.

Mathematically, if the boxes in a layer are given by indices \(i\) for which \(\sum_{i}\,w_i \le W\) and the height of that layer is \(\max_{i}\,h_i\), then the total height is the sum of the heights of all layers. You need to compute the minimum possible total height.

inputFormat

The first line contains two space-separated integers: \(W\) (the fixed storage width) and \(N\) (the number of boxes). The following \(N\) lines each contain two space-separated integers, representing the width and height of a box.

outputFormat

Output a single integer: the minimum total height required to store all boxes.

Note: The answer should be printed to standard output.

10 3
5 4
4 3
3 2

6