Problem Description

To prepare for an exam, Xiao Yang solves problems every day. On the first day, Xiao Yang solves \(a\) problems; on the second day, he solves \(b\) problems. From the third day onwards, the number of problems Xiao Yang solves each day is the sum of the problems solved on the previous two days.

Additionally, Xiao Yang has set a rule for himself: once he solves \(m\) or more problems on a single day, he will stop solving problems for all subsequent days.

Given this, how many problems has Xiao Yang solved by the \(N\)-th day?

Input Format

The input consists of four lines. The first line contains an integer \(a\), the second line contains an integer \(b\), the third line contains an integer \(m\), and the fourth line contains an integer \(N\).

It is guaranteed that \(0 \le a, b \le 10\); \(a, b < m < 1,000,000\); \(3 \le N \le 364\).

Output Format

Output a single integer on one line, representing the total number of problems Xiao Yang has solved by the \(N\)-th day.

Sample Input and Output

Sample Input #1

1
2
10
5

Sample Output #1

19

Sample Input #2

1
1
5
8

Sample Output #2

12

Notes

Sample Explanation 1

On the first day, Xiao Yang solves 1 problem, on the second day, he solves 2 problems, on the third day, he solves \(1+2=3\) problems, on the fourth day, he solves \(2+3=5\) problems, and on the fifth day, he solves \(3+5=8\) problems. Therefore, he has solved a total of \(1+2+3+5+8=19\) problems.

Sample Explanation 2

For the first five days, Xiao Yang solves \(1, 1, 2, 3, 5\) problems respectively. Since on the fifth day he solves 5 problems and \(m=5\), he stops solving problems from then on. Thus, Xiao Yang has solved a total of \(1+1+2+3+5=12\) problems.

见题面 Input 部分

见题面 Output 部分