CSES - Monster Game II | Trò chơi quái vật II

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
tan , kitsune
Dạng bài
Điểm: 2300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn đang chơi một trò chơi bao gồm \(n\) cấp độ. Mỗi cấp độ có một con quái vật. Ở các cấp độ \(1,2,\ldots,n - 1\), bạn có thể giết hoặc trốn thoát khỏi con quái vật. Tuy nhiên, ở cấp độ \(n\), bạn phải giết con quái vật cuối cùng để thắng trò chơi.

Giết một con quái vật tốn \(sf\) thời gian, trong đó \(s\) là sức mạnh của con quái vật và \(f\) là chỉ số kĩ năng của bạn (chỉ số kĩ năng thấp hơn thì tốt hơn). Sau khi giết một con quái vật, bạn nhận được một chỉ số kĩ năng mới. Tổng thời gian tối thiểu mà bạn có thể thắng trò chơi là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): số lượng cấp độ và chỉ số kĩ năng ban đầu.
  • Dòng thứ hai có \(n\) số nguyên \(s_1,s_2,\ldots,s_n\): sức mạnh của mỗi con quái vật.
  • Dòng thứ ba có \(n\) số nguyên \(f_1,f_2,\ldots,f_n\): chỉ số kĩ năng mới của bạn sau khi giết một con quái vật.

Output

  • In một số nguyên: tổng thời gian tối thiểu để thắng trò chơi.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x \le 10^6\)
  • \(1 \leq s_i, f_i \leq 10 ^ 6\)

Example

Sample input

5 100
50 20 30 90 30
60 20 20 10 90

Sample output

2600

Note

Cách tốt nhất để chơi là giết con quái vật thứ hai và thứ năm.

Bình luận