Maximum Points from Locations

You are given a total number of available hours and a set of locations. Each location requires a specific amount of time and awards a certain number of points when spent there. Your task is to determine the maximum points you can earn by spending the available hours optimally among the locations. You may use each location as many times as possible (i.e., the same location can be chosen repeatedly) as long as the required time does not exceed the remaining hours.

The problem can be modeled using dynamic programming. Specifically, if we denote dp[h] as the maximum points obtainable with h hours, then the recurrence can be written in LaTeX as:

\[ \text{dp}[h] = \max_{\substack{i\\t_i \le h}} \{ \text{dp}[h - t_i] + p_i \}\]

where \(t_i\) and \(p_i\) represent the time required and points awarded for the i-th location respectively.

inputFormat

The input is given via STDIN as follows:

1. An integer total_hours representing the total available hours.
2. An integer n representing the number of locations.
3. A line with n space-separated integers representing the time required at each location.
4. A line with n space-separated integers representing the points awarded for each location.

You can assume that 1 ≤ n ≤ 100 and 1 ≤ total_hours ≤ 10³.

outputFormat

Output a single integer to STDOUT representing the maximum points that can be earned given the available hours.

## sample

5
2
1 3
2 5

10

</p>