Hệ Số Sau Mỗi Trạm

Bạn đi qua $n$ trạm theo thứ tự từ $1$ đến $n$. Trạm $i$ có mức tải $s_i$. Ban đầu, hệ số chi phí của bạn là $x$.

Tại mỗi trạm $i<n$, bạn có thể bỏ qua trạm đó hoặc xử lý nó. Trạm $n$ bắt buộc phải được xử lý. Nếu hệ số hiện tại là $c$, việc xử lý trạm có mức tải $s$ tốn $c\cdot s$. Sau khi xử lý trạm $i$, hệ số hiện tại trở thành $f_i$ và được dùng cho lần xử lý tiếp theo.

Hãy tìm tổng chi phí nhỏ nhất để xử lý trạm $n$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $x$.
• Dòng thứ hai chứa $s_1,\dots ,s_n$.
• Dòng thứ ba chứa $f_1,\dots ,f_n$.

Output

• In tổng chi phí nhỏ nhất để xử lý trạm $n$.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $1\le x,s_i,f_i\le 10^6$.
• $s_1\le s_2\le \cdots \le s_n$.
• $x\ge f_1\ge f_2\ge \cdots \ge f_n$.
• Đáp án nằm trong miền số nguyên có dấu $64$-bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 60$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3 5
1 3 6
4 2 1

27