Problem Description

Kaka has started raising rabbits. His mother bought him a pair of newborn rabbits. Kaka learned that the rabbits reproduce as follows: a pair of rabbits will give birth for the first time one month after birth, producing $a$ pairs of rabbits. Then, two months after birth, they will produce $b$ pairs of rabbits. In the third month and every month after that, they will reproduce $c$ pairs of rabbits each month ($a \le b \le c$). We know from the Fibonacci sequence that rabbits can reproduce very quickly. However, Kaka has as many good friends as rabbits, so he wants to have $k$ pairs of rabbits after $m$ months to give them to his friends. Can his wish come true?

[Task] Write a program that reads the input information from the input file; computes how many pairs of rabbits Kaka will have after $m$ months, denoted as $P$; computes the minimum number of pairs of rabbits his mother must buy at the beginning so that Kaka will have at least $k$ pairs of rabbits after $m$ months, denoted as $Q$; and outputs the results to the output file.

Input Format

The first line of the input file contains four positive integers: $a$, $b$, $c$, and $m$. The second line contains only one positive integer $k$. Their meanings are described above.

Output Format

Output two lines. The first line contains an integer $P$, and the second line contains an integer $Q$.

0 1 1 10
10000

89
113

Hint

Constraints: $0 \le a \le b \le c \le 100$, $1 \le m \le 3000$, $1 \le k \le 10^{6000}$.

Translated by ChatGPT 5