Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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] ≤ 10⁶). Dòng cuối gồm N số nguyên B[i] (0 ≤ B[i] ≤ 10⁶). 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