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.|

PTIT018G - ACM PTIT 2018 G - VẬN CHUYỂN HÀNG HÓA

Sau cơn bão, tại khu cảng lớn nhất của đất nước Highland đang có N kiện hàng cứu trợ được tập kết, kiện hàng loại i gồm A[i] khối hàng con. Các kiện hàng được sắp xếp theo thứ tự tăng dần về số lượng. Do đã huy động hầu hết các xe tải vào việc khắc phục sự cố thiên tai, ngày hôm nay chỉ có duy nhất một chiếc xe chở hàng hoạt động ở bến cảng. Mỗi lượt nó chỉ vận chuyển được một khối hàng, sau đó cần phải nạp lại nhiên liệu. Và để tránh bị nhầm lẫn, bác tài xế quyết định vận chuyển từng loại hàng hóa riêng biệt, hết kiện hàng này rồi mới sang kiện hàng khác, không để tình trạng đan xen lẫn lộn xảy ra.

Giá nạp nhiên liệu cho việc chở mỗi loại hàng hóa là khác nhau. Giả sử hiện tại bác tài đang vận chuyển các khối hàng loại i, và loại hàng có nhãn lớn nhất mà bác đã từng vận chuyển là j, giá nạp nhiên liệu mỗi lần cho việc vận chuyển loại hàng i sẽ bằng B[j]. Càng nạp nhiên liệu nhiều lần, giá nhiên liệu càng rẻ. Sau khi vận chuyển được kiện hàng loại N, giá nạp nhiên liệu sẽ bằng 0.

Biết rằng ban đầu chiếc xe đã được nạp đầy nhiên liệu, và loại hàng 1 chỉ có đúng 1 khối hàng. Các bạn hãy giúp bác tài xác định chiến lược để vận chuyển hết N kiện hàng với chi phí nạp nhiên liệu nhỏ nhất có thể.

Input

Dòng đầu tiên là số lượng bộ test T (T ≤ 10). Mỗi test bắt đầu bởi số nguyên N (1 ≤ N ≤ 100 000). Dòng tiếp theo gồm N số nguyên A[i] (1 ≤ A[i] ≤ 106). Dòng cuối gồm N số nguyên B[i] (0 ≤ B[i] ≤ 106). Input đảm bảo rằng A[1] = 1, B[N] = 0, A[1] < A[2] < … < A[N] và B[1] > B[2] > … > B[N].

Output

Với mỗi test, in ra chi phí nhỏ nhất để vận chuyển được hết N kiện hàng.

Example

Input:
2
5
1 2 3 4 6
5 4 3 1 0
6
1 2 3 8 9 10
5 4 3 2 1 0
Output:
26
45

Được gửi lên bởi:Admin
Ngày:2018-05-14
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 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY 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.