#4. 小杨做题

小杨做题

题目描述

为了准备考试,⼩杨每天都要做题。第 11 天,⼩杨做了 aa 道题;第 22 天,⼩杨做了 bb 道题;从第 33 天起,⼩杨每天做的题⽬数量是前两天的总和。

此外,⼩杨还规定,当⾃⼰某⼀天做了⼤于或等于 mm 题时,接下来的所有⽇⼦⾥,他就再也不做题了。

请问,到了第 NN 天,⼩杨总共做了多少题呢?

输入格式

总共 44 ⾏。第⼀⾏⼀个整数 aa ,第⼆⾏⼀个整数 bb,第三⾏⼀个整数 mm ,第四⾏⼀个整数 NN 。 保证 $0 \leq a,b \leq 10;a,b<M \leq 1000000;3 \leq N \leq 364$

输出格式

⼀⾏⼀个整数,表⽰⼩杨 NN 天⾥总共做了多少题⽬。

样例

样例输入1

1
2
10
5

样例输出1

19

样例输入2

1
1
5
8

样例输出2

12

提示

样例解释1:⼩杨第⼀天做 11 题,第⼆天做 22 题,第三天做 1+2=31+2=3 题,第四天做 2+3=52+3=5 题,第五天做 3+5=83+5=8 题。因此他总共做了 1+2+3+5+8=191+2+3+5+8=19

样例解释2:⼩杨前 55 天分别做了 1,1,2,3,51,1,2,3,5 题,由于第 55 天⼩杨做了 55 题,⽽ m=5m=5 ,于是⼩杨从此以后不再做题。因此⼩杨总共做了 1+1+2+3+5=121+1+2+3+5=12 题。

在常规程序中,输⼊、输出时提供提⽰是好习惯。但在本场考试中,由于系统限定,请不要在输⼊、输出中附带任何提⽰信息。