Захисні маски

Limits: 2 sec., 256 MiB

Зеник хоче відвідати \(n\) магазинів у вказаному порядку. Щоб зайти в магазин, він повинен мати захисну маску.

На вході в \(i\)-ий магазин продаються одноразові маски за ціною \(a_i\) та багаторазові за ціною \(b_i\). Зеник купить не більше ніж одну маску на вході в \(i\)-ий магазин. Якщо він придбає одноразову, то використає її тільки в цьому магазині, а потім утилізує. Багаторазову маску можна використовувати в усіх наступних магазинах.

Вам потрібно сказати, яку найменшу суму грошей Зеник витратить на маски.

Input

У першому рядку задано ціле число \(n\) — кількість магазинів, які повинен відвідати Зеник.

У другому рядку задано \(n\) цілих чисел \(a_i\) — ціни одноразових масок у гривнях.

У третьому рядку задано \(n\) цілих чисел \(b_i\) — ціни багаторазових масок у гривнях.

Output

В одному рядку виведіть ціле число — найменшу суму грошей, яку Зеник витратить на маски (у гривнях).

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i, b_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 10 12 15 11 9 8 16 100 200 150 40 47 60 74	77

Input (stdin) сopy	Output (stdout) сopy
7 10 12 15 11 9 8 16 100 200 150 50 47 60 74	81

Notes

У першому прикладі Зенику вигідно купити одноразові маски в перших трьох магазинах і багаторазову в четвертому магазині. Тоді йому доведеться заплатити \(10+12+15+40=77\) (грн).

У другому прикладі вигідно придбати одноразові маски в усіх магазинах.