Interview question of SpringWorks

DESCRIPTION

Tesla is having an army of Highly Advanced Al based Robots. The
robots are designed in such a way that Tesla can fuse 2 robots in order
to make a single robot of an upgraded level. In doing so, the power and
intelligence of both the robots gets fused into that single robot (need
not always increase) and the level of the fused robot gets upgraded i.e.
if two robots of level L₁and L2 gets fused, the final robot obtained is of
level L₁ + L₂. A robot of higher level is always better than a robot of
lower level.

Tesla is having N robots standing in a queue (all of Level 1). He wants
to fuse all the robots into each other in order to make a final robot of
level N. However he can only combine the adjacent robot and there is
an additional cost that Tesla has to incur in order to successfully
perform the fusion. The cost of the fusion depends on the (power,
intelligence) tuple of the robots.

If there are two robots standing adjacent to each other, where the
(power, intelligence) tuple of the first robot is (a, b) and that of the
second robot is (b, c) respectively then the cost of fusion comes out to
be: a *b *c. Also the (power, intelligence) tuple of the resultant robot
is (a,c).

You have to find out the minimum cost that Tesla has to incur in order
to perform this task of fusion.

Note: It is guaranteed that the for all the adjacent robots, the intelligence of the ith robot is same as the power of (i+1)th robot.

Input

• First line of input contains an integer N. describing the number

of robots standing in the queue.

Then N lines follows, each line containing 2 integers representing the power and intelligence of each of the N robots.

Output

A single line which denotes the minimum cost of fusion

Constraints

1 <= N <= 100

1 <= Power <= 1000

1 <= Intelligence <= 1000

Sample test case

Input

3

2.10

10 3

34

Output

84

EXECUTION TIME LIMIT

2 seconds

I think this is simple MCM problem.

if u can provide the solution??