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 $1$ to $3$, and there are initially $E_i$ $(0\le E_i\le 1000)$ pieces of filmmaking equipment on stage $i$.

A sequence of $N$ $(1\le N\le 1000)$ shots will be filmed, one after another, with the $i$-th one taking place on stage $S_i$ $(1\le S_i\le 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.

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 Specification

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\dots N$.

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