Description

魔法学院的植物学家发现了一种特殊魔法植株，该植株遵循以下繁殖规律：
该植株的生长分为两个阶段：幼苗期和成株期； 幼苗需要经过t个月才能长成成株；
成株在长成后的第1个月（即成为成株的第1个月）不产种子；
成株仅在特定的月份产种子，规则如下：
第a₁个月末产p₁颗种子；
第a₂个月末产p₂颗种子；
第a₃个月末产p₃颗种子；
其他月份不产种子，产完p₃后进入休眠，不再产种子。
每颗种子在产出的下一个月会变成一个月龄的幼苗；
初始时：第1个月月初，你有一株刚进入成株期的植株（即它的成株年龄为1个月）；
求第z个月月末时，成株的总数（幼苗不算在结果内）。

Format

Input

第一行输入一个整数t； 接下来三行，每行两个整数，分别表示a₁ p₁、a₂ p₂、a₃ p₃； 最后一行输入一个整数z。

Output

输出一个整数，表示第z个月月末的成株数量。

Samples

2
2 3
5 2
9 1
10

15

Limitation

1 ≤ t ≤ 6
1 ≤ a₁, a₂, a₃ ≤ 12
1 ≤ p₁, p₂, p₃ ≤ 10
t + 1 ≤ z ≤ 50