MIKU2026 - Concert Miku Expo

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Duykhoi1009
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 900 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

MIKU2026 - Concert Miku Expo

Thần tượng ảo Miku_Hatsune chuẩn bị tổ chức tour biểu diễn lớn. Ban tổ chức đã nhận được \(N\) bài hát được đề xuất bởi người hâm mộ. Mỗi bài hát \(i\) có hai thông tin:

  • Thời lượng (\(T_i\)): Thời gian (tính bằng phút) để thể hiện bài hát.
  • Độ yêu thích (\(A_i\)): Mức độ hào hứng của fan khi Miku hát bài này.

Miku_Hatsune muốn chọn ra một danh sách các bài hát biểu diễn trong buổi concert sao cho:

  1. Tổng thời lượng của các bài hát được chọn không vượt quá \(K\) phút (thời lượng tối đa của concert).
  2. Tổng độ yêu thích của các bài hát được chọn là lớn nhất có thể.

Tuy nhiên, Miku_Hatsune có một quy tắc đặc biệt: Nếu hai bài hát có độ yêu thích khác nhau, bài hát nào có độ yêu thích cao hơn bắt buộc phải được ưu tiên xét chọn trước. Nếu hai bài có cùng độ yêu thích, bài hát có thời lượng ngắn hơn sẽ được ưu tiên chọn trước để tiết kiệm thời gian.

Hãy giúp ban tổ chức tính xem tổng độ yêu thích lớn nhất có thể đạt được là bao nhiêu, và số lượng bài hát được chọn tương ứng.

Input

  • Dòng thứ nhất chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5, 1 \le K \le 10^9\)).
  • Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \dots, T_N\) (\(1 \le T_i \le 10^9\)) — thời lượng của từng bài hát.
  • Dòng thứ ba chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) — độ yêu thích của từng bài hát.

Output

  • In ra hai số nguyên phân cách bởi một khoảng trắng: Tổng độ yêu thích lớn nhất và Số lượng bài hát được chọn.

Example

Test 1

Input 
5 10
3 5 2 4 3
10 20 15 12 18
Output 
53 3
Note

Sắp xếp các bài hát theo thứ tự ưu tiên (\(A_i\) giảm dần, \(T_i\) tăng dần):

  1. Bài 2: \(T_2 = 5, A_2 = 20\)
  2. Bài 5: \(T_5 = 3, A_5 = 18\)
  3. Bài 3: \(T_3 = 2, A_3 = 15\)
  4. Bài 4: \(T_4 = 4, A_4 = 12\)
  5. Bài 1: \(T_1 = 3, A_1 = 10\)

Thứ tự chọn lần lượt:

  • Chọn Bài 2 (\(T=5, A=20\)) \(\rightarrow\) Thời gian còn lại: \(10 - 5 = 5\).
  • Chọn Bài 5 (\(T=3, A=18\)) \(\rightarrow\) Thời gian còn lại: \(5 - 3 = 2\).
  • Chọn Bài 3 (\(T=2, A=15\)) \(\rightarrow\) Thời gian còn lại: \(2 - 2 = 0\).

Tổng độ yêu thích: \(20 + 18 + 15 = 53\) với \(3\) bài hát. UwU

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.