34423번 - Delivery Driver 다국어

문제

As a delivery driver for a food delivery service, you can work in one of three different cities each day: Denver, Ft. Collins, or Colorado Springs.

While working for the past few years, you have collected data on your net profit from working in each city and applied a predictive machine learning model that allows you to know exactly how much net profit you can make from working in each city for the next $N$ days.

The model shows that you can make different amounts of money on each day, depending on the location. Naturally, you want to work in the city where you can make the most money each day. However, driving from one city to the next is not without cost, so in some cases it may be better to stay where you are and make slightly less but not have to drive to a different city.

The cost to drive between cities ($c_1$ and $c_2$) is given by $T(c_1, c_2),ドル a constant representing how costly it is to drive from $c_1$ to $c_2$. Note that $T(c_1, c_2)$ is always equivalent to $T(c_2, c_1)$.

You want to determine which city to work in on each of the next $N$ days such that your total net profit across all of the days is maximized. (Net profit is calculated by taking the total earnings and subtracting both the operating costs for each day as well as any transition costs incurred by driving between cities.)

Consider the following example (which describes the first sample input). You are planning for the next 3ドル$ days and have calculated the profit you could make in each of the cities as shown in the table below:

Further, assuming that \begin{align*} T(\text{Denver}, \text{Ft. Collins}) &= \20,ドル \\ T(\text{Denver}, \text{Colorado Springs}) &= \17,ドル \text{and} \\ T(\text{Colorado Springs}, \text{Ft. Collins}) &= \34,ドル \end{align*} if you choose to work from Denver on day 1ドル,ドル Colorado Springs on day 2ドル$ and day 3ドル,ドル then your total net profit would be: \begin{align*} P_\text{total} &= \underbrace{\251ドル}_\text{Day 1ドル$ profit} - \underbrace{\17ドル}_\text{Denver to Colorado Springs} + \underbrace{\151ドル}_\text{Day 2ドル$ profit} + \underbrace{\402ドル}_\text{Day 3ドル$ profit} = \787ドル \end{align*} whereas if you chose to work from Denver on day 1ドル,ドル Colorado Springs on day 2ドル,ドル and Ft. Collins on day 3ドル,ドル then your total net profit would be: \begin{align*} P_\text{total} &= \underbrace{\251ドル}_\text{Day 1ドル$ profit} - \underbrace{\17ドル}_\text{Denver to Colorado Springs} + \underbrace{\151ドル}_\text{Day 2ドル$ profit} - \underbrace{\34ドル}_\text{Colorado Springs to Ft. Collins} + \underbrace{\410ドル}_\text{Day 3ドル$ profit} = \761ドル. \end{align*}

Clearly, the first option is better! Even though it may be tempting to go to Ft. Collins on Day 3ドル,ドル the cost of driving there from Colorado Springs is too great.

Can you write a program which tells you which city to work from for each of the next $N$ days such that total net profit $P$ across all of the days is maximized? Note that you can start and end in any city you wish, and the start and end cities do not have to be the same.

입력

The first line contains three, space-separated integers representing the values of $T (\text{Denver}, \text{Ft. Collins}),ドル $T (\text{Denver}, \text{Colorado Springs}),ドル and $T (\text{Colorado Springs}, \text{Ft. Collins}),ドル respectively.

The next line contains a single integer 2ドル \leq N \leq 100,ドル the number of days that you have to plan for.

The next 3ドル$ lines contain a list of $N$ space-separated integers representing the potential profit for the next $N$ days in Denver, Ft. Collins, and Colorado Springs, respectively.

All monetary numbers will be integers between 0ドル$ and 100ドル,000円$.

출력

The first and only line of output is the maximum total net profit $P$ across all $N$ days in dollars.

제한

노트