Maximum Cakes Production

You are given amounts of three ingredients: flour \(F\), sugar \(S\), and eggs \(E\). In addition, there are \(N\) types of cakes available. Each cake type \(i\) requires a fixed amount of flour \(f_i\), sugar \(s_i\), and eggs \(e_i\) to make one cake.

Your task is to choose a cake type (ignoring those that require zero in any ingredient) and produce as many cakes as possible using the available ingredients. For each valid cake type, the maximum number of cakes you can produce is calculated as:

\(\text{cakes}_i = \min\Big(\left\lfloor\frac{F}{f_i}\right\rfloor, \left\lfloor\frac{S}{s_i}\right\rfloor, \left\lfloor\frac{E}{e_i}\right\rfloor\Big)\)

Output the maximum number of cakes that can be produced among all the cake types. If no cake type is valid (for example, when all cake types include a zero requirement) then output 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains three integers \(F\), \(S\), and \(E\) — the amounts of flour, sugar, and eggs available.
• The second line contains a single integer \(N\) — the number of cake types.
• This is followed by \(N\) lines, each containing three integers \(f_i\), \(s_i\), and \(e_i\) representing the amounts required of flour, sugar, and eggs for the \(i\)-th cake type.

outputFormat

Output a single integer — the maximum number of cakes that can be produced using one of the valid cake types, printed to standard output (stdout). If none of the cake types can be produced, print 0.

10 10 10
2
2 2 2
1 1 1

10