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

Đ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}$ .

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_{i}, f_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
5 100 50 20 30 90 30 60 20 20 10 90	2600	Tiêu diệt quái vật 2 (tốn 20×100=2000) rồi tiêu diệt quái vật 5 (tốn 30×20=600). Tổng: 2600.
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.