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 1\,000)~ pieces of filmmaking equipment on stage ~i~.

A sequence of ~N~ ~(1 \le N \le 1\,000)~ 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.