Maximize Points Within Time Limit

You are given a limited amount of time \(H\) hours and a list of \(m\) matches. Each match \(i\) has two associated integers: \(p_i\) representing the points earned if participated, and \(t_i\) representing the hours required to play that match.

The goal is to choose a subset of these matches such that the total playing time does not exceed \(H\) and the total points earned is maximized. A greedy strategy is suggested: sort the matches by the ratio \(\frac{p_i}{t_i}\) in descending order and then accumulate matches until adding another match would exceed \(H\). Note that the value \(m\) represents the number of matches available.

Input Constraints: \(H\) can be any non-negative integer, and \(m\) is the number of matches (possibly zero). Each match is defined by two integers \(p_i\) and \(t_i\). It is guaranteed that the input follows this format.

inputFormat

The first line contains two integers \(H\) and \(m\), where \(H\) is the total available hours and \(m\) is the number of matches.

The next \(m\) lines each contain two integers \(p\) and \(t\), representing the points earned and the hours required for a match, respectively.

All input is provided via standard input (stdin).

outputFormat

Output a single integer representing the maximum total points that can be earned without exceeding the available \(H\) hours. The result should be printed to standard output (stdout).

10 3
100 2
200 3
150 5

450