Nướng Bánh Trung Thu


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type

Một cửa hàng bánh Trung Thu nọ đang chuẩn bị cho một ngày làm việc tất bật. Cửa hàng dự kiến làm \(N\) mẻ bánh trung thu. Mẻ bánh thứ \(i\) dự kiến được nướng vào thời gian \(a_i\) và nướng trong \(b_i\) thời gian. Không có hai mẻ nào bắt đầu nướng cùng một lúc. Chủ tiệm đã sắp xếp các mẻ bánh này theo thời gian từ sớm đến muộn.

Hiện tại, chủ cửa hàng đã đầu tư \(K\) lò nướng. Trong mỗi thời gian, mỗi lò chỉ nướng được một mẻ bánh. Để mọi thứ tuân theo một quy trình, chủ tiệm đưa ra một nguyên tắc cơ bản: Xử lí bánh theo thứ tự thời gian, nếu còn lò nướng trống cho một mẻ, nướng mẻ đó. Ngược lại, ngay lập tức đưa đi cấp đông. Chủ quán đang tập trung vào quy trình chứ chưa cần tối ưu, vì vậy, việc chọn cấp đông một mẻ cần nướng lâu để nướng thêm các mẻ khác là chưa cần thiết trong lúc này.

Hãy cho biết, số mẻ bánh được đem đi cấp đông là bao nhiêu.

Lưu ý: Khi một mẻ bánh nướng xong trùng với thời gian bắt đầu một mẻ khác, thì mẻ tiếp theo có thể cho vào nướng ngay lập tức.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên \(N, K \ (1\le N, K \le 10^5)\);
  • Dòng thứ hai chứa \(N\) số nguyên \(a_i \ (1\le a_i \le 10^9; a_1 < a_2 < a_3 < ... < a_N)\);
  • Dòng thứ ba chứa \(N\) số nguyên \(b_i \ (1\le b_i \le 10^9)\).

Kết quả

  • Kết quả bài toán.

Chấm điểm

  • Subtask 1 (60%): \(N,K \le 10^3\).
  • Subtask 2 (40%): Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

5 2
1 2 3 4 5
2 1 3 3 2

output

1

Comments

There are no comments at the moment.