Bạn đang kẹt trong một trò chơi và phải đối đầu với ~n~ con quái vật. Thanh kiếm hiện tại của bạn có thể gây ~1~ sát thương và tốn ~k~ năng lượng. Con quái vật thứ ~i~ có lượng máu là ~a_i~. Bạn giết được một con quái vật khi máu của nó là ~0~ hoặc thấp hơn, và bạn sẽ lấy được thanh kiếm của nó. Thanh kiếm của con quái vật thứ ~i~ gây ~1~ sát thương và tốn ~k_i~ năng lượng.

Nhiệm vụ của bạn là tính xem cần tối thiểu bao nhiêu năng lượng để giết hết ~n~ con quái vật.

Input

• Dòng đầu tiên chứa hai số ~k, n~, (~2 \le n \le 10^5~)
• Dòng thứ hai chứa ~n~ số ~a_1, a_2, ..., a_n~, (~1 \le a_1 < a_2 < ... < a_n \le 10^9~)
• Dòng thứ ba chứa ~n~ số ~k_1, k_2, ..., k_n~, (~0 = k_n < k_{n-1} < ... < k_1 < k \le 10^9~)

Output

Một số duy nhất là kết quả bài tin.

Examples

Input

2 2
1 10
1 0

Output

12