Xiaoyang's Problem Solving

Problem Description

To prepare for an exam, Xiaoyang does problems every day. On day 1, he does $a$ problems; on day 2, he does $b$ problems; starting from day 3, the number of problems he does each day is the sum of the previous two days.

In addition, Xiaoyang has a rule: once he does greater than or equal to $m$ problems on some day, he will never do any problems again for all the following days.

By day $N$, how many problems has Xiaoyang done in total?

Input Format

Four lines in total. The first line is an integer $a$, the second line is an integer $b$, the third line is an integer $m$, and the fourth line is an integer $N$.

Output Format

One line with one integer, the total number of problems Xiaoyang did in $N$ days.

Sample Input

Sample Input 1

1
2
10
5

Sample Input 2

1
1
5
8

Sample Output

Sample Output 1

19

Sample Output 2

12

Sample Explanation

Xiaoyang does 1 problem on day 1, 2 on day 2, 3 ($1+2$) on day 3, 5 ($2+3$) on day 4, and 8 ($3+5$) on day 5. In five days he did $1+2+3+5+8=19$ problems.

Constraints

Guaranteed $0 \le a, b \le 10$, $a, b < m < 10^6$, $3 \le N \le 364$.