Bộ nhớ máy ảnh

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Nam vừa sở hữu một chiếc điện thoại Mobile VN hiện đại nhất trang bị camera kép và có thẻ nhớ dung lượng là \(d\) megabytes (MB). Với nhiều chế độ lựa chọn điều chỉnh máy ảnh mà ta có thể lưu giữ những kỉ niệm đáng nhớ với những bức ảnh có chất lượng đỉnh cao nhất. Một bức ảnh chụp ở chế độ tiết kiệm bộ nhớ nhất của máy sẽ chiếm dung lượng ít nhất là \(a\) MB trong không gian trống trong thẻ nhớ. Một bức ảnh ở chế độ chụp có chất lượng cao sẽ chiếm dung lượng là \(b\) MB của không gian trống trong thẻ nhớ.

Hôm nay Nam sẽ sử dụng điện thoại của mình để chụp ảnh cho các bạn trong lớp. có \(n\) bạn được chụp ảnh (đánh số thứ tự từ 1 đến \(n\)), bạn thứ \(i\) sẽ yêu cầu Nam chụp cho cho bạn ấy \(x_i\) bức ảnh chất lượng thấp và \(y_i\) bức ảnh chất lượng cao.

Em giúp Nam đưa ra phương án hợp lý để có thể chụp được ảnh cho nhiều bạn nhất.

Input

  • Dòng 1 chứa hai số nguyên dương \(n,\ d\) (\(1 \le n \le 10^5, 1 \le d \le 10^9\))
  • Dòng 2 chứa hai số nguyên dương \(a,\ b\) (\(1 \le a \le b \le 10^4\))
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(x_i,\ y_i\) (\(0 \le x_i, y_i \le 10^5\)) – Số lượng bức ảnh chất lượng thấp và số lượng bức ảnh chất lượng cao của bạn thứ \(i\) yêu cầu.

Output

  • Chứa số \(k\) – số lượng khách hàng được phục vụ nhiều nhất

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(n \le 20\).
  • Subtask \(2\) (\(25\%\) số điểm): \(n \le 1000\).

Example

Test 1

Input
3 10
2 3
1 4
2 1
1 0
Output
2
Note

Giải thích: Hai bạn được chọn chụp ảnh là 2 và 3


Bình luận

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