Woburn Challenge 2015-16 Round 1 - Junior Division

Problem 4: Trip Budgeting

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 simple 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_min (1 ≤ E_min ≤ 10⁹) 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_base, H_base, and F_base (1 ≤ T_base, H_base, F_base ≤ 10⁷).
• There are N (1 ≤ N ≤ 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 ≤ E_i, T_i, H_i, F_i ≤ 10⁷).
  • If attended, the i-th attraction (for i = 1..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_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_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_base subtract the F_i for each attraction i that was attended. The base food cost cannot go below zero – after F_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_min units of excitement for the overall trip. It is guaranteed that this is possible.

Input Format

Line 1 will contain four space-separated integers in the following order: E_min, T_base, H_base, and F_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..N) will contain four space-separated integers: E_i, T_i, H_i, and F_i.

Output Format

Output a single integer – the minimum cost (in dollars) required to achieve at least E_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 24600 dollars. The costs are calculated as follows:

• Transportation costs 2000 + 300 + 100 + 500 + 400 = 3300 dollars.
• The most expensive hotel across all of the attractions being attended costs 20000 dollars.
• Food was original going to cost 4000 dollars, but 400 + 800 + 1000 + 500 = 2700 dollars were saved by eating at the venues of the attractions.

Thus, the total cost of the trip is 3300 + 20000 + (4000 − 2700) = 24600 dollars. In fact, this is the best possible answer.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 17, 2015
Authors: Alex, SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

E_min can actually be as low as 0, not 1.
Unfortunately, data reflecting this has already been used in the live contest.
Fortunately, from inspecting the submissions, it did not appear to have actually impacted anybody's ranks.

WHY WA?Only 30/50