Description

蓓蓓朋友快过生日了，于是，她决定自己亲手做些珍珠项链作为生日礼物。她打算买$N$种不同颜色的珍珠来组成$M$完美项链。一条$M$完美项链是由$M$颗不同颜色的珍珠组成的。请你帮她算出最多可以组成多少条$M$完美项链。

Format

Input

多组测试数据，每组测试数据三行。

第一行为珍珠颜色的种类$1\le N\le 1000$。

第二行为每种颜色的数量，数量不超过$2000$。

第三行为完美项链的$M(1\le M\le 100)$。

如果$N$为$0$时终止测试。

Output

每组测试数据输出一行最多可以$M$完美项链的条数。

Samples

5
3 3 3 3 3
5
6
1 2 3 4 5 6
5
0

3
3