# Letter/Blog Writer Coding Problem (using Dynamic Programming)

**Shivang** is a blog writer and he is working on two websites simultaneously. He has to write two types of blogs which are:

**Technical blogs for website_1**: **X** of this type can be written in an hour. (**X** will be the input)
**Fun blogs for website_2**: **Y** of this type can be written in an hour. (**Y** will be input)

You are to help him to save time. Given **N** number of total blogs, print the **minimum number of hours he needs to put for combination of both the blogs**, so that no time is wasted.

Input:
N: number of total blogs
X: number of Technical blogs for website_1 per hour
Y: number of Fun blogs for website_2 per hour
Output:
Print the minimum number of hours Shivang needs to write the
combination of both the blogs (total N).
If it is NOT possible, print "−1".

**Example:**

Input:
N: 33
X: 12
Y: 10
Output:
-1
Input:
N: 36
X: 10
Y: 2
Output:
6 (10*3+2*3)

**Explanation:**

For the first case,
No combination is possible that's why output is -1.
For the second test case,
Possible combinations are 30 technical blogs (3 hours) + 6 fun blogs (3 hours)
20 technical blogs (2 hours) + 16 fun blogs (8 hours)
10 technical blogs (1 hours) + 26 fun blogs (13 hours)
0 technical blogs (0 hours) + 36 fun blogs (18 hours)
So, best combination is the first one which takes total 6 hours

**The problem is basically solving equation,**

**aX + bY = N** where we need to find the valid integer coefficients of **X** and **Y**. Return **a+b** if there exists such else return **-1**.

We can find a recursive function for the same too,

Say,

f(n) = minimum hours for n problems
f(n) = min(f(n-x) + f(n-y)) if f(n-x), f(n-y) is solved already

We can convert the above recursion to DP.

Converting the recursion into DP:

C++ Implementation:Output