## WC '18 Finals S1 - Behind the Scenes

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
##### Woburn Challenge 2018-19 Finals Round - Senior Division

The cows and monkeys of Scarberia, their long-standing conflicts well behind them at last, have banded together to produce a historical drama documenting their past battles. With the Head Monkey as writer and producer, and the director's chair occupied by the cows' leader, Bo Vine, this will be a collaborative masterpiece to remember!

Today, a full day of filming is set to take place at the monkeys' and cows' joint studios. The studios feature three sound stages, numbered from to , and there are initially pieces of filmmaking equipment on stage .

A sequence of shots will be filmed, one after another, with the -th one taking place on stage . Whenever a shot is filmed on a certain stage, there must be no equipment present on that stage at the time. Right before each shot, Bo Vine may choose or more pieces of equipment to be moved. Each such piece will be moved from its current stage to a different stage of Bo's choice, at the cost of tipping a stagehand , and will remain there until potentially moved again later.

What's the minimum total cost of stagehand tips which Bo Vine will need to dispense such that each of the shots will have no equipment present on its stage at filming time?

#### Input Specification

The first line of input consists of three space-separated integers, , , and .
The next line consists of a single integer, .
lines follow, the -th of which consists of a single integer, , for .

#### Output Specification

Output a single integer, the minimum total cost of stagehand tips required, in dollars.

#### Sample Input

6 3 4
5
3
2
2
1
2

#### Sample Output

17

#### Sample Explanation

One possible optimal strategy for Bo Vine is as follows:

• Before the st shot, move all pieces of equipment from stage to stage .
• Before the nd shot, move all pieces of equipment from stage to stage , and all pieces of equipment from stage to stage .

This requires in stagehand tips.