Woburn Challenge 2015-16 Round 1 - Junior Division

The PEG trip at the end of the school year is a long-lasting tradition of the club. The leaders usually decide on three teams (junior, intermediate, and senior) based on whom they find to be most attentive and hard-working throughout the years. Then, the deserving teams are taken to some place in the USA (a different city every year!) where they will compete, and most probably dominate, in the American Computer Science League (ACSL) All-Star competition. The trip will then consist of several action-packed days of competing, dining, frolicking, and touring the local attractions. While most PEG students who are selected to go are simply enlightened by the fantastic opportunity, few of them are aware of the rigorous planning and budgeting that takes place behind the scenes.

Budgeting is a complex task. We must account for transportation, hotel, food, and most importantly – attractions. Choices must be made in each of these categories with consideration for how much money is going to be spent, and how exciting the trip is expected to be. To make each trip memorable enough for the PEG history books, the PEG leaders would like this year's trip to have at least an excitement level of ~E_{\text{min}}~ ~(1 \le E_{\text{min}} \le 10^9)~ units. Funding has always been a complicated matter due to Woburn's Student Activity Council (SAC). The SAC is willing to help the club satisfy its minimal excitement level, provided that it is done in the cheapest way possible. The cost and excitement of the trip will be calculated with the following rules:

• The base costs of transportation, hotel, and food in dollars are respectively ~T_{\text{base}}~, ~H_{\text{base}}~, and ~F_{\text{base}}~ ~(1 \le T_{\text{base}}, H_{\text{base}}, F_{\text{base}} \le 10^7)~.
• There are ~N~ ~(1 \le N \le 20)~ attractions numbered from ~1~ to ~N~. The team can attend each attraction at most once.
  • Each attraction has an ~E_i~, ~T_i~, ~H_i~, and ~F_i~ value associated with it ~(0 \le E_i, T_i, H_i, F_i \le 10^7)~.
  • If attended, the ~i~-th attraction (for ~i = 1 \dots N~) will contribute ~E_i~ units of excitement to the overall trip.
  • By going to a particular attraction, money may be saved or extra money may be spent. For instance, the team might have to pay extra transportation costs to reach the event. The team might also have to pick a more expensive hotel in order to be close enough to attend it. Conversely, many attractions provide free food, so the team might actually save money on food.
  • By choosing attraction ~i~, the team must be prepared to also pay an additional ~T_i~ dollars for transportation on top of ~T_{\text{base}}~. That is, the overall transportation cost is the sum of the base transportation cost and the transportation costs incurred across all of the attractions they decide to visit.
  • Each attraction has an associated hotel nearby that costs ~H_i~ dollars to stay at. Since the team will not be attending more than one hotel, we have to prepare for the worst and assume that the overall hotel cost for the entire trip will be the maximum of ~H_{\text{base}}~ and ~H_i~ across all of the attractions that the team eventually decides to attend.
  • By choosing attraction ~i~, the team will actually save ~F_i~ dollars on food because it will be provided at the venue. That is, the overall food cost will be the base food cost ~F_{\text{base}}~ subtract the ~F_i~ for each attraction ~i~ that was attended. The base food cost cannot go below zero – after ~F_{\text{base}}~ has been reduced to zero, attending additional attractions will have no effect on the nonexistent overall food cost.
• The total cost of the trip is equal to the sum of the overall costs of transportation, hotel, and food respectively.
• The excitement of the trip is equal to the sum of ~E_i~ across all of the attractions that the team decides to attend.

Given this, please help the PEG leaders determine the minimum possible total cost that will produce at least ~E_{\text{min}}~ units of excitement for the overall trip. It is guaranteed that this is possible.

Input Specification

Line ~1~ will contain four space-separated integers in the following order: ~E_{\text{min}}~, ~T_{\text{base}}~, ~H_{\text{base}}~, and ~F_{\text{base}}~.
Line ~2~ will contain a single integer ~N~.
There will be ~N~ lines to follow. The ~i~-th of these lines (for ~i = 1 \dots N~) will contain four space-separated integers: ~E_i~, ~T_i~, ~H_i~, and ~F_i~.

Output Specification

Output a single integer – the minimum cost (in dollars) required to achieve at least ~E_{\text{min}}~ units of excitement on the trip.

Sample Input

50 2000 20000 4000
5
30 300 20000 400
40 500 30000 2000
10 100 15000 800
30 500 11000 1000
20 400 20000 500

Sample Output

24600

Explanation

The team wants to achieve a minimum of ~50~ units of excitement, and has given the five attractions with excitement ratings of ~30~, ~40~, ~10~, ~30~, and ~20~ respectively. By choosing every attraction except for number ~2~, the team is actually able to achieve ~90~ units of excitement at a cost of ~24\,600~ dollars. The costs are calculated as follows:

• Transportation costs ~2\,000 + 300 + 100 + 500 + 400 = 3\,300~ dollars.
• The most expensive hotel across all of the attractions being attended costs ~20\,000~ dollars.
• Food was originally going to cost ~4\,000~ dollars, but ~400 + 800 + 1\,000 + 500 = 2\,700~ dollars were saved by eating at the venues of the attractions.

Thus, the total cost of the trip is ~3\,300 + 20\,000 + (4\,000 - 2\,700) = 24\,600~ dollars. In fact, this is the best possible answer.