| UFPE Starters Final Try-Outs 2025 |
|---|
| Finished |
The marathonists went to the summer school in Campinas. Now they need to get to Unicamp to participate in the contest. They decided to use a ride-hailing app, Gabmobile. In this app, the user selects the departure and destination locations and has access to ride options from multiple drivers. Each driver asks for a certain price and will only take a certain maximum number of passengers.
The marathonists want to spend as little as possible to go to Unicamp, but they are too tired from training every day to find out the best way to choose the ride options. So they need your help. Given that $$$X$$$ marathonists went to the summer school, there are $$$N$$$ available ride options and that the $$$i$$$-th ride options is offered by a driver which only wants to take a maximum of $$$p_i$$$ passengers and asks for $$$v_i$$$ reals for the trip to Unicamp, what is the minimum possible total value spent by the marathonists to get to Unicamp?
The first line of input contains two integers, $$$X$$$ and $$$N$$$ ($$$0 \lt X, N \leq 10^3$$$), the number of marathonists in the summer school and the number of available ride options, respectively. Following, there are $$$N$$$ lines. The $$$i$$$-th one contains two integers, $$$p_i$$$ ($$$0 \lt p_i \leq 4$$$) and $$$v_i$$$ ($$$0 \lt v_i \leq 10^9$$$), the number of passengers the $$$i$$$-th driver will take and how much they charge for the trip, respectively.
Output an integer $$$Y$$$, the minimum possible total value spent by the marathonists to go to Unicamp. If there is no way for them to get there, output $$$-1$$$.
6 33 104 203 8
18
6 23 102 5
-1
| Name |
|---|


