Trò Chơi Quái Vật I

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bạn đang tiến qua $n$ màn chơi, mỗi màn có một con quái vật. Bạn phải tiêu diệt quái vật ở màn cuối cùng (màn $n$ ), nhưng có thể bỏ qua bất kỳ quái vật nào ở các màn $1$ đến $n - 1$ .

Ban đầu bạn có hệ số kỹ năng $x$ . Khi tiêu diệt quái vật $i$ với hệ số kỹ năng hiện tại $f$ , bạn mất $s_{i} \cdot f$ thời gian và hệ số kỹ năng của bạn cập nhật thành $f_{i}$ .

Đặc tính: Độ mạnh của quái vật không giảm ( $s_{1} \leq s_{2} \leq \dots \leq s_{n}$ ) và hệ số kỹ năng không tăng ( $x \geq f_{1} \geq f_{2} \geq \dots \geq f_{n}$ ).

Hãy tìm tổng thời gian tối thiểu để hoàn thành tất cả các màn.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $x$ .
Dòng 2: $n$ số nguyên $s_{1}, s_{2}, \dots, s_{n}$ — độ mạnh của các quái vật.
Dòng 3: $n$ số nguyên $f_{1}, f_{2}, \dots, f_{n}$ — hệ số kỹ năng sau khi tiêu diệt mỗi quái vật.

Dữ liệu ra

Một số nguyên — tổng thời gian tối thiểu.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq x \leq 10^{6}$
$1 \leq s_{1} \leq s_{2} \leq \dots \leq s_{n} \leq 10^{6}$
$x \geq f_{1} \geq f_{2} \geq \dots \geq f_{n} \geq 1$

Ví dụ

Input	Output	Giải thích
5 100 20 30 30 50 90 90 60 20 20 10	4800	Tiêu diệt quái vật 3 (tốn 30×100=3000) rồi tiêu diệt quái vật 5 (tốn 90×20=1800). Tổng: 4800.
1 5 3 2	15	Chỉ có 1 màn — phải tiêu diệt quái vật duy nhất: 3×5=15.

Bình luận

Không có bình luận tại thời điểm này.