AT_abc275_h [ABC275Ex] Monster

[problemUrl]: https://atcoder.jp/contests/abc275/tasks/abc275_h 数直線上に $ N $ 匹のモンスターが並んでおり、座標 $ i $ $ (1\leq\ i\leq\ N) $ には 体力 $ A_i $ のモンスターがいます。 また、座標 $ i $ にはつねに強さ $ B_i $ のバリアが張られています。 このバリアは、その座標にいるモンスターの体力が $ 0 $ 以下となった後も存在し続けます。 魔法使いである高橋君は次の操作を好きなだけ行うことができます。 - $ 1\leq\ l\leq\ r\leq\ N $ をみたす整数 $ l,r $ を選ぶ。 - $ \max(B_l,B_{l+1},\ldots,B_r) $ だけ魔力を消費して、座標 $ l,l+1,\ldots,r $ にいるモンスターの体力を $ 1 $ 減らす。 $ l,r $ を選ぶ際、座標 $ l,l+1,\ldots,r $ のいずれかに、すでに体力が $ 0 $ 以下のモンスターのいるような選び方をしても構いません。 ただし、その場合でも各座標にあるバリアは消えていないことに注意してください。 高橋君の目標は全てのモンスターの体力を $ 0 $ 以下にすることです。 目標を達成するために必要な魔力の総和としてあり得る最小の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $

目標を達成するために必要な魔力の総和の最小値を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 高橋君は次のように操作を行うことで、目標を達成することができます。 - 高橋君は $ (l,r)=(1,5) $ を選びます。魔力を $ \max(10,40,20,60,50)=60 $だけ消費して、操作後の各モンスターの体力は $ (3,2,4,0,1) $ となります。 - 高橋君は $ (l,r)=(1,5) $ を選びます。魔力を $ \max(10,40,20,60,50)=60 $だけ消費して、操作後の各モンスターの体力は $ (2,1,3,-1,0) $ となります。 - 高橋君は $ (l,r)=(1,3) $ を選びます。魔力を $ \max(10,40,20)=40 $だけ消費して、操作後の各モンスターの体力は $ (1,0,2,-1,0) $ となります。 - 高橋君は $ (l,r)=(1,1) $ を選びます。魔力を $ \max(10)=10 $だけ消費して、操作後の各モンスターの体力は $ (0,0,2,-1,0) $ となります。 - 高橋君は $ (l,r)=(3,3) $ を選びます。魔力を $ \max(20)=20 $だけ消費して、操作後の各モンスターの体力は $ (0,0,1,-1,0) $ となります。 - 高橋君は $ (l,r)=(3,3) $ を選びます。魔力を $ \max(20)=20 $だけ消費して、操作後の各モンスターの体力は $ (0,0,0,-1,0) $ となります。 このとき、消費した魔力の総和は $ 60+60+40+10+20+20=210 $ となり、このときが最小となります。