Use any Programming Language to implement below

A chef has G grams of flour. The chef can make one piece of bread that needs g0 gram of flour, and he can sell it for p0.

He can also make N types of cake such that each one needs a special flavor.

He has Gr[i] gram of the special flavor for the ith cake such that each cake require R[i] gram of its special flavor and A[i] gram of flour and he can sell it with a price P[i].

It is given the chef can make any number of bread without special flavors or he can

make cakes using its special flavor and flour unless he runs out of flour or the required

special flavor.

Find the maximum amount of money the chef can earn.

Input Format

The first line contains an integer, G, denoting the amount of flour.

The next line contains an integer, N, denoting the number of elements in Gr.

The next line contains an integer, g0, denoting the amount of flour to make one bread.

The next line contains an integer, p0, denoting the price of one bread. Each line of the N subsequent lines (where 0

Input Format The first line contains an integer, G, denoting the amount of flour. The next line contains an integer, N, denoting the number of elements in Gr. The next line contains an integer, go, denoting the amount of flour to make one bread. The next line contains an integer, po, denoting the price of one bread. Each line i of the N subsequent lines (where 0 si