SDE - Intern

Ninja is a boy who lives in ninjaland. Every day, during the morning he gets 1 coin from his mother. He wants to buy exactly ‘N’ candies. Each of the candies cost 2 coins usually and 1 coin if it is on sale. Ninja has to buy exactly K[i] candies of the i-th type(he buys candies in the evening).

Ninjas can buy any(possibly zero) number of candies of any type during any day(if he has enough money to do it). If the candy is on sale he can buy it for 1 coin and otherwise he has to buy it for 2 coins.

There are ‘M’ special offers in the candy shop. The j-th offer (D[j], C[j]) means that candies of the C[j]-th type are on sale during the D[j]-th day.

Ninja wants to buy all candies as soon as possible. Your task is to calculate the minimum day when he can buy all the candies.

You are given ‘N’ types of umbrellas, where each umbrella can shelter some number of people. Given the number of people each umbrella can shelter in the array “UMBRELLA”, you need to determine the minimum number of umbrellas required to cover exactly ‘M’ people with umbrellas.

Note -

You have an infinite number of umbrellas of each type.
If it is not possible to shelter exactly ‘M’ people then print -1. 

This year Santa Claus got a magic bag for bringing gifts for children. So magical thing about this magic bag is that, whenever the number of gifts inside the bag becomes strictly less than 'K' gifts, it automatically refills back to its full capacity(say its capacity is of 'N' gifts). Now a child can ask for 'M' (some positive integer less than 'N') gifts from Santa. This reduces the number of gifts in the bag by 'M'.

On the occasion of Christmas, when Santa Claus arrived, children of your locality made a queue for taking gifts from Santa Claus. But some greedy kids can ask for more gifts than the current number of gifts in the bag which is regarded as invalid demand and that kid doesn't get any gift.

You are watching this distribution of gifts, and become curious about knowing the number of gifts remaining in Santa's bag after giving gifts to a kid. You get the ordered list of demands of kids as 'DEMANDS', can you tell which are invalid demands and how many gifts left in the bag if the demand is valid?

Note:

1. You can assume Magic Bag is completely filled initially.

2. If the demand by a kid is invalid print -1 which will denote this invalid demand.

Who is your role model?

Tell me about yourself.