#PY0027. Dance Dance Revolution DDR

Dance Dance Revolution DDR

Description

HH最近迷上了跳舞机(Dance Dance Revolution , DDR),他想有一天人家会叫他“舞蹈家HH”。

DDR的主要内容是用脚来踩踏板。踏板有4个方向的箭头,用1、2、3、4表示,如图所示。

img

每首歌曲有一个箭头序列,游戏者必须按照这个序列一次用某一只脚踩相应的踏板。在任何时候,两只脚不能在同一个踏板上,但可以同时在中心位置0。

每一个时刻,HH必须移动他的一只脚去踩相应的箭头,另一只脚不能动。每跳完一个曲子,HH会计算他的总体力消耗。

规定:

从中心移动到任意一个箭头耗费2单位体力;

从任何一个箭头到相邻的箭头耗费3单位体力;

从一个箭头到相对的箭头耗费4单位体力;

留在原地再踩一下耗费1单位体力。

HH想花尽量少的体力,你能帮助他么?

Format

Input

一个含有1234的序列,以0结束,代表一首歌曲。

Length < = 100000

Output

一个整数,表示最小耗费体力

Samples

1 2 3 4 1 2 3 3 4 2 0
22