### 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`≤ 10

_{min}^{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`,_{base}`H`, and_{base}`F`(1 ≤_{base}`T`,_{base}`H`,_{base}`F`≤ 10_{base}^{7}). - 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`, and_{i}`F`value associated with it (0 ≤_{i}`E`,_{i}`T`,_{i}`H`,_{i}`F`≤ 10_{i}^{7}). - If attended, the
`i`-th attraction (for`i`= 1..`N`) will contribute`E`units of excitement to the overall trip._{i} - 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`dollars for transportation on top of_{i}`T`. That is, the_{base}*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`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_{i}*overall hotel cost*for the entire trip will be the maximum of`H`and_{base}`H`across all of the attractions that the team eventually decides to attend._{i} - By choosing attraction
`i`, the team will actually*save*`F`dollars on food because it will be provided at the venue. That is, the_{i}*overall food cost*will be the base food cost`F`subtract the_{base}`F`for each attraction_{i}`i`that was attended. The base food cost cannot go below zero – after`F`has been reduced to zero, attending additional attractions will have no effect on the nonexistent overall food cost._{base}

- Each attraction has an
- 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`across all of the attractions that the team decides to attend._{i}

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`, and

_{base}`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`, and

_{i}`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)

Alexon Oct 19, 2015 - 1:23:25 am UTC CorrectionUnfortunately, 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.

jasonhaha25on Oct 18, 2015 - 5:19:40 am UTC WA