You recently got hired by a company in Orlando, and you've decided to take advantage of all of the theme parks there. You and your friends have coordinated and decided on the days in the coming year that you wish to visit the theme park.
Now, you need to buy tickets. The theme park offers several types of ticket: each ticket type has a certain price and grants you admission to the park for a certain number of consecutive days. (You don't have to attend the park on all of those days if you don't want to; but you won't get a refund for unused days!). You can buy multiples of each ticket type and you may assume that all ticket types are available starting on all days of the year (no day is sold out).
What is the cheapest total cost you need to pay for admission to the park on your chosen days?
The first line of input contains two space-separated integers $$$D$$$ and $$$T$$$: the number of days you wish to visit the park $$$(1 \leq D \leq 365)$$$ and the number of ticket types available $$$(1 \leq T \leq 10).$$$ The next line contains $$$D$$$ strictly increasing space-separated integers $$$d_i$$$ $$$(1 \leq d_i \leq 365)$$$: the days of the year that you want to visit the theme park. Each of the final $$$T$$$ lines describe a ticket type. Each line has contains two space-separated integers $$$k$$$ and $$$p$$$: the number of consecutive days that you can enter the park using a ticket of this type $$$(1 \leq k \leq 365)$$$; and the cost of the ticket in dollars $$$(1 \leq p \leq 10\,000)$$$.
Print an integer: the fewest dollars you need to spend for admission to the park on all of your chosen days, assuming you buy tickets optimally.
6 22 4 7 9 364 3651 1007 199
498
6 31 2 3 4 5 63 1006 2505 150
200
One optimal way to buy tickets for Sample Input 1 is to buy two 7-day tickets and one 1-day ticket. The 7-day tickets covers days (2, 4, 7) and (364, 365), and the 1-day ticket covers day 9.
