题目背景

中科信息第一次月赛第一题。

题目描述

中国航天事业迅猛发展。航天员飞往宇宙需要带上充足的物资，如水，面包，氧气，氮气。但是飞船携带物资有限，而地面物资无限，现给出飞船各种载物能力和地面物资种类，每种物资可以选无限多个，并给出每种物资携带量与生存天数的比例关系，求宇航员最多能在太空住几天。

注意：物资承载能力互不干扰，天数只能为整数，不考虑发射与返航时所消耗的物资，四种载物能力限制分别为重量限制，体积限制，物质的量限制，资金限制。

Input

第一行：一个整数n，代表物资的种类。
第二行：四个整数a，b，c，d，分别代表飞船上的重量限制，体积限制，物质的量限制，资金限制。
第三行：一个整数q，代表单位能量能使航天员存活q天。
接下来n行：每行五个整数，分别代表这种物资的重量，体积，物质的量和需花费的资金。

Output

一个整数，表示航天员在太空最多能存活的天数。

Sample 1

Input

4
10 20 30 40
3
1 2 3 4 5
2 5 1 1 3
1 3 2 6 8
1 1 4 4 1

Output

159

Limitation

Old Test Data:\(2 \le n \le 50 \), \( 1 \le a,b,c,d \le 20,30,40,50\), \( 1 \le e,f,g,h, \le a,b,c,d \), \( 1 \le q \le 20\).
Now Test Data:\(2 \le n \le 1000 \), \( 1 \le a,b,c,d \le 50\), \( 1 \le e,f,g,h, \le a,b,c,d \), \( 1 \le q \le 20\).
Normally spreaking,the old one is the right limition,but maybe the datas too weak and low,suitable time and space limitions more closed to the new one.(Chinese Sytle English)
1s, 128MiB for each test case.