[AHOI2006]斐波卡契的兔子（kacci）

卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子。卡卡了解到兔子的繁殖规律是这样的：

• 刚出生的一对兔子在一个月后将第一次生出一胎 $a$ 对兔子；
• 接着在出生后的第二个月又将生出 $b$ 对兔子；
• 在第三个月和以后的每个月都会繁殖 $c$ 对兔子。

其中 $a\le b\le c$。

由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友。卡卡想在 $m$ 个月后有 $k$ 对兔子，以便分给他的好友们，他的愿望是否能够实现呢？

你需要编写一个程序：

1. 计算 $m$ 个月后卡卡将有多少对兔子，设之为 $P$；
2. 计算如果 $m$ 个月后卡卡要拥有至少 $k$ 对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为 $Q$。

输入格式

第一行有 $4$ 个正整数 $a, b, c, m$。

第二行仅含一个正整数 $k$。

它们的含义见上文描述。

输出格式

输出两行，第一行是一个整数 $P$，第二行是一个整数 $Q$。

样例输入

0 1 1 10
10000

样例输出

89
113

数据范围

• $0\le a\le b\le c\le 100$；
• $1\le m\le 3000$；
• $1\le k\le 10^{6000}$。

来源与许可

本题为 AHOI 2006 试题「斐波卡契的兔子（kacci）」，题面与测试数据整理自 BZOJ 1265。

样例 1

输入

0 1 1 10
10000

输出

89
113