Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money. 

The manager of logging factory wants them to go to the jungle and cut n trees with heights a_1, a_2, ..., a_{n}. They bought a chain saw from a shop. Each time they use the chain saw on the tree number i, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is i (the tree that have height a_{i} in the beginning), then the cost of charging the chain saw would be b_{i}. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each i < j, a_{i} < a_{j} and b_{i} > b_{j} and also b_{n} = 0 and a_1 = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost. 

They want you to help them! Will you?


-----Input-----

The first line of input contains an integer n (1 ≤ n ≤ 10^5). The second line of input contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The third line of input contains n integers b_1, b_2, ..., b_{n} (0 ≤ b_{i} ≤ 10^9).

It's guaranteed that a_1 = 1, b_{n} = 0, a_1 < a_2 < ... < a_{n} and b_1 > b_2 > ... > b_{n}.


-----Output-----

The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
5
1 2 3 4 5
5 4 3 2 0

Output
25

Input
6
1 2 3 10 20 30
6 5 4 3 2 0

Output
138

Difficulty: competition

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * n
stk = [0]
for i in range(1, n):
    while len(stk) > 1 and c[stk[1]] - c[stk[0]] <= a[i] * (b[stk[0]] -
            b[stk[1]]):
        del stk[0]
    c[i] = c[stk[0]] + a[i] * b[stk[0]]
    while len(stk) > 1 and ((c[stk[-1]] - c[stk[-2]]) * (b[stk[-1]] - b[i]) >
            (b[stk[-2]] - b[stk[-1]]) * (c[i] - c[stk[-1]])):
        del stk[-1]
    stk.append(i)
print(c[n - 1])


n = int(input())

a = [0 for i in range(0, n + 1)]
b = [0 for i in range(0, n + 1)]

a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [0 for i in range(0, n + 1)]

c = [[0 for i in range(0, 3)] for j in range(0, n + 1)]

stack = []
stack.append(0)
stack.append(1)

dp[0] = 0
dp[1] = a[1] * b[0]

def intersection(x, y):
    return int((dp[y] - dp[x]) / (b[x] - b[y]))

last = 0
c[last] = [0, intersection(0, 1), 0]
last+=1
c[last] = [intersection(0, 1), 1000000001, 1]
last1=0
for i in range(2, n):

    while (last1 >= 0):
        if (c[last1][0] <= a[i] and c[last1][1] >= a[i]):
            dp[i] = dp[c[last1][2]] + b[c[last1][2]] * a[i]
            #print(i,dp[i])
            break
        elif c[last1][0] > a[i]:
            last1 -= 1
        else:
            last1 += 1

    while stack:
        top = stack[-1]
        if len(stack) >= 2:
            second_top = stack[-2]
            if intersection(second_top, i) < intersection(top,second_top):
                stack.pop()
                last -= 1
            else:
                break
        else:
            break

    stack.append(i)
    last += 1
    c[last] = [intersection(top, i),1000000001,i]
    c[last-1]= [c[last-1][0],intersection(top,i),c[last-1][2]]

print(dp[n-1])

N = 100100

def main():
    n = int(input())
    d=[0]*N
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    m,c=[0]*N,[0]*N
    m[0] = b[0]
    c[0] = d[0]
    
    z = 1
    p = 0
    for i in range(1,n):
        p = min(p,z)
        while(p+1<z and m[p+1]*a[i]+c[p+1]<=m[p]*a[i]+c[p]):
            p=p+1
        d[i] = m[p]*a[i]+c[p]
        while(z>=2 and (c[z-2]-c[z-1])*(b[i]-m[z-1])>=(c[z-1]-d[i])*(m[z-1]-m[z-2]) ):
            z=z-1
        m[z],c[z]=b[i],d[i]
        z=z+1
    #for j in range(n):print(d[j])
    print(d[n-1])

main()


read = lambda: map(int, input().split())
n = int(input())
a = list(read())
b = list(read())
dp = [0] * n
st = [0]
def f1():
    i0, i1 = st[0], st[1]
    b1 = dp[i1] - dp[i0]
    k1 = b[i0] - b[i1]
    return b1 <= a[i] * k1
def f2():
    i1, i2 = st[-1], st[-2]
    k1, k2 = b[i1] - b[i], b[i2] - b[i1]
    b1, b2 = dp[i] - dp[i1], dp[i1] - dp[i2]
    return b2 * k1 > b1 * k2
for i in range(1, n):
    while len(st) > 1 and f1(): st.pop(0)
    dp[i] = dp[st[0]] + a[i] * b[st[0]]
    while len(st) > 1 and f2(): st.pop()
    st.append(i)
print(dp[n - 1])

read = lambda: list(map(int, input().split()))
n = int(input())
a = list(read())
b = list(read())
dp = [0] * n
ch = [0]


def get(i, x):
    return b[i] * x + dp[i]


def f1():
    if len(ch) < 2:
        return 0
    return get(ch[0], a[i]) >= get(ch[1], a[i])


def f2():
    if len(ch) < 2:
        return 0
    i1 = ch[-1]
    x = (dp[i1] - dp[i]) / (b[i] - b[i1])
    return get(ch[-2], x) <= get(i, x)


for i in range(1, n):
    while f1():
        ch.pop(0)
    dp[i] = get(ch[0], a[i])
    while f2():
        ch.pop()
    ch.append(i)
print(dp[n - 1])


f = lambda: list(map(int, input().split()))
g = lambda j: a[i] * b[j] + t[j]
h = lambda j, k: (t[i] - t[j]) * (b[j] - b[k]) < (t[j] - t[k]) * (b[i] - b[j])

n = int(input())
a, b = f(), f()
t = [0] * n
p = [0]
for i in range(1, n):
    while len(p) > 1 and g(p[1]) < g(p[0]): p.pop(0)
    t[i] = g(p[0])
    while len(p) > 1 and h(p[-2], p[-1]): p.pop()
    p.append(i)
print(t[-1])

N = 100100

def main():
    n = int(input())
    d=[0]*N
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    m,c=[0]*N,[0]*N
    m[0] = b[0]
    c[0] = d[0]
    
    z = 1
    p = 0
    for i in range(1,n):
        p = min(p,z)
        while(p+1<z and m[p+1]*a[i]+c[p+1]<=m[p]*a[i]+c[p]):
            p=p+1
        d[i] = m[p]*a[i]+c[p]
        while(z>=2 and (c[z-2]-c[z-1])*(b[i]-m[z-1])>=(c[z-1]-d[i])*(m[z-1]-m[z-2]) ):
            z=z-1
        m[z],c[z]=b[i],d[i]
        z=z+1
    #for j in range(n):print(d[j])
    print(d[n-1])

main()




# Made By Mostafa_Khaled


n = int(input())
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = [0]*n
st = [0]*n
first=0
second=0    
for i in range(1,n):
    #Delete from front until the value of lines is increasing w.r.to value a[i]
    while(second-first>0 and a[i] * b[st[first]] + c[st[first]] >= a[i] * b[st[first+1]] + c[st[first+1]]):
    	first = first + 1;
    c[i] = a[i] * b[st[first]] + c[st[first]];
    #Delete from back until the intersection of lines last two lines in stack is to the left of the new line and the last line 
    while(second-first>0 and (b[st[second]] - b[i])*(c[st[second]] - c[st[second-1]]) > (c[i] - c[st[second]])*(b[st[second-1]] - b[st[second]])):
    	second = second-1;
    second = second+1
    st[second] = i;
print(c[n-1]);

from collections import deque

class line:
    def __init__(self, k, b):
        self.k = k
        self.b = b

    def get(self, x):
        return self.k * x + self.b

def check(l1, l2, nl):
    return (nl.b - l2.b) * (l1.k - l2.k) - (nl.k - l2.k) * (l1.b - l2.b) <= 0

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

hull = deque()
hull.append(line(b[0], 0))
for i in range(1, n):
    arg = a[i]
    while len(hull) > 1 and hull[0].get(arg) >= hull[1].get(arg):
        hull.popleft()
    ans = hull[0].get(arg)
    nl = line(b[i], ans)
    while len(hull) > 1 and check(hull[-2], hull[-1], nl):
        hull.pop()
    hull.append(nl)

print(ans)



n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[0]*(n)
st=[0]
for i in range(1,n):
    while len(st)>1 and dp[st[0]] + b[st[0]]*a[i]>dp[st[1]] + b[st[1]]*a[i]:
        st.pop(0)
    dp[i]=dp[st[0]] + b[st[0]]*a[i]
    while len(st)>1 and (dp[st[-2]] - dp[st[-1]])*(b[st[-2]] - b[i]) < (dp[st[-2]] - dp[i])*(b[st[-2]] - b[st[-1]]):
        st.pop()
    st.append(i)
print(dp[-1])    


aa, bb, dp = [], [], []

def dot(i, a):
    return dp[i] + a*bb[i]

def main():
    n = int(input())
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))

    for k in range(n):
        dp.append(0)
        aa.append(a[k])
        bb.append(b[k])

    st, i, j = [0 for _ in range(n) ], 0,  0

    for k in range(1,n):
        while(j - i > 0 and dot(st[i],a[k]) >= dot(st[i+1],a[k])):
            i+=1
        dp[k] = a[k]*b[st[i]] + dp[st[i]]
        while(j - i > 0 and (b[st[j]] - b[k])*(dp[st[j]] - dp[st[j-1]]) > (dp[k] - dp[st[j]])*(b[st[j-1]] - b[st[j]])):
            j-=1
        j+=1
        st[j] = k


    print(dp[-1])

def __starting_point():
    main()
__starting_point()

def dot(a, b, c):
    return a + c*b

def main():
    n = int(input())
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    dp = [ 0 for _ in range(n) ]
    st = [0 for _ in range(n) ]
    i, j = 0,  0

    for k in range(1,n):
        while(j - i > 0 and dot(dp[st[i]],b[st[i]],a[k]) >= dot(dp[st[i+1]],b[st[i+1]],a[k])):
            i+=1
        dp[k] = a[k]*b[st[i]] + dp[st[i]]
        while(j - i > 0 and (b[st[j]] - b[k])*(dp[st[j]] - dp[st[j-1]]) > (dp[k] - dp[st[j]])*(b[st[j-1]] - b[st[j]])):
            j-=1
        j+=1
        st[j] = k


    print(dp[-1])

def __starting_point():
    main()
__starting_point()

def cross(i, j, k, b, cost):
    # k, i, j
    return (cost[i] - cost[j]) * (b[i] - b[k]) - (b[i] - b[j]) * (cost[i] - cost[k])


def dot(i, j, a, b, cost):
    return cost[j] + a[i] * b[j]


def CF319C():
    N = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    cost = [0] * N
    hull = [0] * N  # Make hull considering total minimum cost and charge of individual trees

    left = 0
    right = 1 # Index of items in hull
    for i in range(1, N):
        # Find the last cut tree which incurs minimum cost for ith tree
        while left + 1 < right and dot(i, hull[left], a, b, cost) >= dot(i, hull[left + 1], a, b, cost):
            # Only increase left when it decreases cutting cost
            left += 1

        cost[i] = dot(i, hull[left], a, b, cost)

        while right >= 2 and cross(hull[right], hull[right - 1], i, b, cost) >= 0:
            right -= 1
        if left >= right: left = right - 1
        right += 1
        hull[right] = i

    return cost[-1]


def __starting_point():
    res = CF319C()
    print(res)
__starting_point()

def cross(i, j, k, b, cost):
    # k, i, j
    return (cost[i] - cost[j]) * (b[i] - b[k]) - (b[i] - b[j]) * (cost[i] - cost[k])


def dot(i, j, a, b, cost):
    return cost[j] + a[i] * b[j]


def CF319C():
    N = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    cost = [0] * N
    hull = [0] * N  # Make hull considering total minimum cost and charge of individual trees

    left = 0
    right = 1 # Index of items in hull
    for i in range(1, N):
        # Find the last cut tree which incurs minimum cost for ith tree
        while left + 1 < right and dot(i, hull[left], a, b, cost) >= dot(i, hull[left + 1], a, b, cost):
            # Only increase left when it decreases cutting cost
            left += 1

        cost[i] = dot(i, hull[left], a, b, cost)

        while right >= 2 and cross(hull[right], hull[right - 1], i, b, cost) >= 0:
            right -= 1

        right += 1
        hull[right] = i

    return cost[-1]


def __starting_point():
    res = CF319C()
    print(res)
__starting_point()

# referenced dukkha

def cross(i, j, k, b, cost):
    return (cost[i] - cost[j]) * (b[i] - b[k]) - (b[i] - b[j]) * (cost[i] - cost[k])


def dot(i, j, a, b, cost):
    return cost[j] + a[i] * b[j]


def CF319C():
    N = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    cost = [0] * N
    hull = [0] * N  # Make hull considering total minimum cost and charge of individual trees

    left = 0
    right = 1 # Index of items in hull
    for i in range(1, N):
        # Find the last cut tree which incurs minimum cost for ith tree
        while left + 1 < right and dot(i, hull[left], a, b, cost) >= dot(i, hull[left + 1], a, b, cost):
            # Only increase left when it decreases cutting cost
            left += 1

        cost[i] = dot(i, hull[left], a, b, cost)

        while right >= 2 and cross(hull[right], hull[right - 1], i, b, cost) >= 0:
            right -= 1

        right += 1
        hull[right] = i

    return cost[-1]


def __starting_point():
    res = CF319C()
    print(res)
__starting_point()

#d_n= [C_m+A_n*B_m] for m in range()
#A=[ ->> ]
#B=[ <<- ]

def intersection(p,q):
    return (q[1]-p[1])/(p[0]-q[0])

def tree_cutting(n,A,B):
    I=[[0,0] for _ in range(n)]
    C=[0 for _ in range(n)]
    
    C[0]=0
    I[0][0]=-float("inf")
    I[0][1]=float("inf")
    C[1]=C[0]+A[1]*B[0]
    hull=[[B[0],C[0]],[B[1],C[1]]]
    I[0][1]=intersection(hull[-1],hull[-2])
    I[1][0]=I[0][1]
    I[1][1]=float("inf")
    curr=1
    k=0
    for i in range(2,n):
        k=min(k,curr)-1
        while True:
            k+=1
            if I[k][0]<=A[i] and A[i]<=I[k][1]:
                j=k
                break
        C[i]=hull[k][1]+A[i]*hull[k][0]
        p=[B[i],C[i]]

        while intersection(p,hull[-2])<=intersection(hull[-1],hull[-2]):
            hull.pop()
            curr-=1
            if len(hull)<2: break
        if B[i]!=hull[-1][0]:
            hull.append(p)
            I[curr][1]=intersection(hull[-1],hull[-2])
            curr+=1
            I[curr][0]=intersection(hull[-1],hull[-2])
            I[curr][1]=+float("inf")
        else:
            I[curr][1]=+float("inf")
    return C[n-1]

def __starting_point():
    n=int(input())
    A=list(map(int,input().strip().split()))
    B=list(map(int,input().strip().split()))
    print(tree_cutting(n,A,B))
__starting_point()

n=int(input())
A=list(map(int,input().strip().split()))
B=list(map(int,input().strip().split()))
C=[0 for _ in range(n)]
hullx=[0 for _ in range(n)]
hully=[0 for _ in range(n)]    
    
sz=-1
p=0

def intersection(p,q):
    nonlocal hullx,hully
    return (hully[q]-hully[p])/(hullx[p]-hullx[q])
def insert(B,C):
    nonlocal sz,p,hullx,hully
    sz+=1
    hullx[sz]=B
    hully[sz]=C
    while sz>1 and intersection(sz-1,sz-2)>=intersection(sz-1,sz):
        hullx[sz-1]=hullx[sz]
        hully[sz-1]=hully[sz]
        sz-=1
def query(x):
    nonlocal sz,p,B,C
    p=min(sz,p)
    while sz>0 and p<sz and intersection(p,p+1)<=x: p+=1
    return hully[p]+hullx[p]*x


C[0]=0
insert(B[0],0)

for i in range(1,n):
    C[i]=query(A[i])
    insert(B[i],C[i])
print(C[n-1])


n=int(input())
A=list(map(int,input().strip().split()))
B=list(map(int,input().strip().split()))
C=[0 for _ in range(n)]
hullx=[0 for _ in range(n)]
hully=[0 for _ in range(n)]    
    
sz=-1
p=0

def intersection(p,q):
    nonlocal hullx,hully
    return (hully[q]-hully[p])/(hullx[p]-hullx[q])
def insert(B,C):
    nonlocal sz,p,hullx,hully
    sz+=1
    hullx[sz]=B
    hully[sz]=C
    while sz>1 and intersection(sz-1,sz-2)>=intersection(sz-1,sz):
        hullx[sz-1]=hullx[sz]
        hully[sz-1]=hully[sz]
        sz-=1
def query(x):
    nonlocal sz,p,B,C
    p=min(sz,p)
    while sz>0 and p<sz and intersection(p,p+1)<=x: p+=1
    return hully[p]+hullx[p]*x


C[0]=0
insert(B[0],0)

for i in range(1,n):
    C[i]=query(A[i])
    insert(B[i],C[i])
    
print(C[n-1])


n=int(input())
A=list(map(int,input().strip().split()))
B=list(map(int,input().strip().split()))

def tree_cutting(n,A,B):
    C=[0 for _ in range(n)]
    hullx=[0 for _ in range(n)]
    hully=[0 for _ in range(n)]    
    
    sz=0
    p=0

    C[0]=0
    hullx[0]=B[0]
    hully[0]=C[0]

    for i in range(1,n):
        p=min(sz,p)
        while sz>0 and p<sz and (hully[p+1]-hully[p])/(hullx[p]-hullx[p+1])<=A[i]:
            p+=1
        C[i]=hully[p]+hullx[p]*A[i]
        sz+=1
        hullx[sz]=B[i]
        hully[sz]=C[i]
        while sz>1 and (hully[sz-2]-hully[sz-1])/(hullx[sz-1]-hullx[sz-2])>=(hully[sz-2]-hully[sz])/(hullx[sz]-hullx[sz-2]):
            hullx[sz-1]=hullx[sz]
            hully[sz-1]=hully[sz]
            sz-=1
    return C[n-1]
    
print(tree_cutting(n,A,B))