题目背景

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

题目描述

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

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

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

\(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\).
1s, 128MiB for each test case.