Maximum Books on the Shelf

Problem Description:

You are given a shelf with a maximum width \(w\) and a collection of books. Each book is represented by a triple \((\text{width},\,\text{height},\,\text{thickness})\). Your task is to determine the maximum number of books that can be placed on the shelf without exceeding the shelf's width. The strategy is to sort the books in ascending order by their width, and then select books one by one until adding another book would exceed the shelf's width.

Example: If \(w = 100\) and the books' widths are \([10, 20, 30, 40, 50]\) (after sorting), then you can place the first four books since \(10+20+30+40=100\), but adding the book with width 50 would exceed the shelf's capacity.

inputFormat

The first line contains two integers \(w\) and \(n\) separated by a space, where \(w\) is the width of the shelf and \(n\) is the number of books.

Each of the following \(n\) lines contains three integers representing the width, height, and thickness of a book. These values are separated by spaces.

outputFormat

Output a single integer, which is the maximum number of books that can be placed on the shelf without exceeding the width \(w\).

100 5
10 200 50
20 150 70
30 100 90
40 50 110
50 30 130

4