### Woburn Challenge 2018-19 Finals Round - Senior Division

## Problem 1: Behind the Scenes

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 1 to 3, and there are initially `E _{i}` (0 ≤

`E`≤ 1000) pieces of filmmaking equipment on stage

_{i}`i`.

A sequence of `N` (1 ≤ `N` ≤ 1000) shots will be filmed, one after another, with the `i`-th one taking place on stage `S _{i}` (1 ≤

`S`≤ 3). 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 0 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 $1, and will remain there until potentially moved again later.

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

### Input Format

The first line of input consists of three space-separated integers, `E`_{1}, `E`_{2}, and `E`_{3}.

The next line consists of a single integer, `N`.

`N` lines follow, the `i`-th of which consists of a single integer, `S _{i}`, for

`i`= 1..

`N`.

### Output Format

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 1st shot, move all 4 pieces of equipment from stage 3 to stage 2.
- Before the 2nd shot, move all 6 pieces of equipment from stage 1 to stage 3, and all 7 pieces of equipment from stage 2 to stage 3.

This requires $4 + $6 + $7 = $17 in stagehand tips.

All Submissions

Best Solutions

**Point Value:** 8 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** May 18, 2019

**Author:** SourSpinach

**Languages Allowed:**

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

## Comments (Search)

It's quiet in here...