问题描述

为了准备考试，小杨每天都要做题。第1天做了a道题，第2天做了b道题；从第3天起，每天做的题目数量是前两天的总和。此外，小杨规定：当自己某一天做了大于或等于m题时，接下来的所有日子里再也不做题。 请问到了第N天，小杨总共做了多少题？

输入描述

共4行输入：

• 第1行：整数a
• 第2行：整数b
• 第3行：整数m
• 第4行：整数N

数据范围：$0 \leq a,b \leq 10$，$a,b < m \leq 10^6$，$3 \leq N \leq 364$

输出描述

输出一行一个整数，表示小杨N天里总共做的题目数量。

特别提醒：请不要在输入、输出中附带任何提示信息。

样例输入1

1
2
10
5

样例输出1

19

样例解释1

小杨第1天做1题，第2天做2题，第3天做1+2=3题，第4天做2+3=5题，第5天做3+5=8题。所有天数的做题量均小于10，因此总题数为1+2+3+5+8=19。

样例输入2

1
1
5
8

样例输出2

12

样例解释2

小杨前5天分别做了1、1、2、3、5题，第5天做题量等于m=5，因此之后不再做题。总题数为1+1+2+3+5=12。