Bờm đang thực hiện đăng ký học phần cho khóa học tiếp theo và cậu cũng có kế hoạch rút ngắn thời gian học bằng cách đăng ký nhiều tín chỉ nhất cho từng khóa học.
Danh sách gồm có n môn học, môn học thứ i có độ khó aᵢ và số tín chỉ bᵢ.
Để tiến độ học tập đúng kế hoạch, Bờm cần chọn đăng ký học các môn sao cho tổng số tín chỉ không được ít hơn C.
Bên cạnh đó, để đảm bảo hiệu quả học tập, các môn phải được chọn học theo trình tự có độ biến động nhỏ nhất.
Độ biến động được định nghĩa là giá trị chênh lệch độ khó lớn nhất giữa hai môn học liền kề.
Cụ thể, nếu đăng ký học m môn theo trình tự i₁, i₂, …, iₘ thì:
Độ biến động = max(|aᵢ₁ - aᵢ₂|, |aᵢ₂ - aᵢ₃|, …, |aᵢₘ₋₁ - aᵢₘ|)
Hãy giúp Bờm chọn đăng ký các môn học sao cho:
n, C (1 ≤ n ≤ 2×10⁵; 1 ≤ C ≤ 10⁹) -số lượng môn học và tổng số tín chỉ tối thiểu phải đăng ký.a₁, a₂, …, aₙ — độ khó của các môn (1 ≤ aᵢ ≤ 10⁹) - độ khó của các môn học.b₁, b₂, …, bₙ — số tín chỉ của các môn (1 ≤ bᵢ ≤ 10⁹) - số tín chỉ của các môn học.C không vượt quá tổng số tín chỉ của tất cả n môn học.Ghi ra thiết bị ra chuẩn một số nguyên là độ biến động nhỏ nhất của danh sách các môn học có tổng số tín chỉ không ít hơn C.
Ví dụ:
Đầu vào:
5 10
8 3 1 5 2
6 4 2 6 5
Đầu ra:
1
Giải thích:
Đầu vào:
5 15
8 3 1 5 2
6 4 2 6 5
Đầu ra:
2
Đầu vào:
3 5
1 3 6
2 3 4
Đầu ra:
2
Đầu vào:
4 6
10 20 30 40
1 2 3 4
Đầu ra:
10
Đầu vào:
5 10
1 2 3 100 101
2 2 2 3 3
Đầu ra:
97
Đầu vào:
1 1
5
1
Đầu ra:
0
Đầu vào:
6 8
1 4 5 6 10 11
1 2 2 2 1 1
Đầu ra:
4
Đầu vào:
5 7
1 100 101 102 103
1 2 2 2 2
Đầu ra:
1
Đầu vào:
4 5
1 5 9 13
2 2 2 2
Đầu ra:
4
Đang tải editor...