Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P156SUMI - ROUND 6I - Chặt cây

Cho n cây có chiều cao lần lượt là a[1], a[2], …, a[n]. Bạn có một chiếc cưa, mỗi lần cưa có thể giảm chiều cao của một cây đi 1 đơn vị, và phải thực hiện hoàn tất việc cưa chiếc cây này. Tuy nhiên, bạn cần nạp thêm xăng cho chiếc cưa để nó có thể hoạt động liên tục. Chiếc cưa sẽ được bổ sung năng lượng với chi phí bằng b[k], trong đó k là chỉ số lớn nhất của những chiếc cây đã bị chặt. Một cây được coi là đã bị chặt khi chiều cao của nó bằng 0. Nếu như chưa có cây nào bị chặt, bạn sẽ không thể nạp năng lượng cho chiếc cưa.

Nhiệm vụ của bạn là tính ra chi phí nhỏ nhất để có thể chặt được tất cả n cây.

Biết rằng dãy a[] là một dãy tăng dần, còn dãy b[] là một dãy giảm dần, và a[1] = 1, b[n] = 0. Bạn sẽ được cung cấp đủ lượng xăng để hạ đổ cây 1 đầu tiên.

Input

Dòng đầu tiên là số nguyên n (1 <= n <= 10^5).

Dòng thứ 2 chứa n số nguyên a[1], a[2],…, a[n] (1 <= a[i] <= 10^9).

Dòng thứ 3 chứa n số nguyên b[1], b[2],…, b[n] (1 <= b[i] <= 10^9).

Output

In ra một số nguyên là kết quả bài toán.

Example

Input:

7

1 2 3 4 5 6 7

6 5 4 3 2 1 0

Output: 42
Giải thích test: Chặt cây 1 đầu tiên, sau đó chặt cây 7. Để chặt cây 7, cần nạp xăng 7 lần, mỗi lần tốn chi phí bằng b[1] = 6. 
Sau khi hạ xong cây 7, tất cả các còn lại có thể hạ đổ mà không tốn năng lượng, do chi phí nạp năng lượng bằng b[7] = 0 
cho mỗi lần cưa. Tổng chi phí bằng 7*6 = 42.

Được gửi lên bởi:Admin
Ngày:2015-08-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.