Alignprocess Identifying Recurring Character Sequences in Keywords - Flipkart Grid 8 Round 3

Problem Preview

"Aymeline owns a microprocessor fabrication plant, which has N robots (R₁ to R_N) to manufacture different varieties of microprocessors. Microprocessors (or chips) are one of the most complex products in the world, and creating these chips is a difficult and precise process. The robots work on a particular chip in sequence i.e. first R₁ works on the chip, then R₂, and so on until R_N. When R_N finishes its part, the chip is ready for dispatch. As these chips are very delicate and can't be stored anywhere until completely fabricated, once a robot has finished its job on a chip, it should immediately pass it on to the next robot without any delay. For that reason, the robot receiving the chip has to be free and should not be working on any other chip. For this reason, Aymeline has programmed the first robot such that it waits for the least possible amount of time before working on a new chip so she is certain that all of the downstream activities go through without problems. Each robot Rᵢ has a time standard Tᵢ and each chip Fⱼ has a fabrication complexity. The time required by Rᵢ to finish its job on a particular chip is computed as the product TᵢFⱼ. Aymeline has got an order from a client to manufacture M different chips. She plans to produce the chips in order 1 to M. The client wants to know the time when all the M chips will be ready for dispatch. Given a Robot times and a fabrication complexity, write a program to help Aymeline determine the time required for fabricating all the M chips. Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings while reading the input or while printing, as these contribute to the standard output. **Constraints:** - 1 <= N <= 100000 - 1 <= M <= 100000 - 1 <= Tᵢ <= 10000 - 1 <= Fⱼ <= 10000 **Input Format:** First line of input contains two space-separated integers N and M, where N is number of robots and M is number of chips. Second line contains N space-separated integers which denotes the time Tᵢ (in minutes) taken by iᵗʰ robot. Third line contains M space-separated integers which denotes the fabrication complexity Fⱼ of the jᵗʰ chip. **Output Format:** Output contains a single integer, which is the minimum time (in minutes) required to dispatch all the M chips. **Sample Input 1:** ``` 3 3 2 1 1 2 1 1 ``` **Sample Output 1:** ``` 11 ``` **Explanation:** After four minutes, R1 finishes working on the first chip. It might start working on the second chip immediately, but that would violate a condition that chips have to be passed to next robots as soon as they're done (after seven minutes second robot would finish working on its part of second chip, but the third robot would not be free to take over as it would still be working on the first chip). That is the reason production of the second chip is started after five minutes. Production of the third chip starts after seven minutes. First chip is finished after eight, second after nine and third after eleven minutes. Total time is then 11. **Sample Input 2:** ``` 3 3 2 3 3 2 1 2 ``` **Sample Output 2:** ``` 29 ```"