小李每天都扶老奶奶过马路，这样助人为乐的行为感动了幸运之神，幸运之神决定庇佑小李在接下来的 n 天时间内，每天都能捡到金币。第 1 天，小李捡到 a 个金币；第 2 天，小李捡到 b 个金币；从第 3 天起，小李每天捡到的金币数量是前两天的总和。 但是小李知道做人不能太贪心，当他某一天捡到了大于或等于 m 个金币时，接下来的所有日子里，即使遇到金币也不会捡起来了。 试计算小李这 n 天一共捡了多少金币。

输入描述

总共 4 行。第一行一个整数 a，第二行一个整数 b，第三行一个整数 m，第四行一个整数 n。 保证 0 ≤ a,b ≤ 10；a,b < m < 1,000,000；3 ≤ n ≤ 364。

输出描述

一行一个整数，表示小李这 n 天一共捡了多少金币。

输入样例1

1
2
10
5

输出样例1

19

输入样例2

1
1
5
8

输出样例2

12

提示

【样例解释 1】 小李第一天捡到 1 个，第二天捡到 2 个，第三天捡到 1+2=3 个，第四天捡到 2+3=5 个，第五天捡到 3+5=8 个。因此他总共捡到 1+2+3+5+8=19 个。

【样例解释 2】 小李前 5 天分别捡到 1,1,2,3,5 个，由于第 5 天小李捡到 5 个，而 m=5，于是小李从此以后不再捡金币。因此小李总共捡到 1+1+2+3+5=12 个。