QUESTION: Mark has to cross river. There are N rocks in the river. Each rock i has a weight denoted by A[i].
Mark can jump from ith rock to the nearest jth rock if i<j<=N and either of these conditions satisfy:

• A[j]>=A[i] and there is no k such that A[k]>=A[i], where i<k<j.
• A[j]<A[i] and there is no k such that A[k]<A[i], where i<k<j.

Now, each rock absorbs some energy from mark's body. The ith rock absorbs val[i] energy from mark's body. You have to find the minimum energy mark has to use to reach Nth rock. Initially, Mark is on 1st rock.

Determine the minimum energy Mark has to use to reach Nth rock.

EXAMPLE1: If N=3, A=[2, 1, 3] and val=[5, 2, 8]

• Mark jumps from 1st rock to 3rd rock.
• Energy consumed is val[1] + val[3] = 5 + 8 =13.
• This is the minimum among all possible paths.
• Thus, the answer is 13.

EXAMPLE2: If N = 5, A= [4, 3, 5, 2, 6] and
val = [3, 2, 4, 1, 5]

• The path for this case is rock with indices : 1->2->4->5.
• The energy absorbed is val[1] + val[2] + val[4] + val[5] = 3 + 2 +1 + 5 = 11, which is the minimum among all possible paths.
• Thus, the answer is 11.