Ghép Cặp Tương Thích

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John quản lý $N$ loại ID bò khác nhau. Mỗi loại ID $d_{i}$ có $n_{i}$ con bò mang ID đó. Hai con bò khác nhau có thể giao tiếp nếu tổng ID của chúng bằng $A$ hoặc $B$ . Mỗi con bò tham gia tối đa một cặp. Tìm số cặp giao tiếp lớn nhất.

Lưu ý: hai con bò cùng ID vẫn có thể ghép cặp nếu $2 \times d = A$ hoặc $2 \times d = B$ .

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $A$ , $B$ .
$N$ dòng tiếp theo: Hai số nguyên $n_{i}$ và $d_{i}$ .

Dữ liệu ra

Một số nguyên — số cặp tối đa.

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$
$0 \leq d_{i} \leq 10^{9}$
$1 \leq n_{i} \leq 10^{9}$
$0 \leq A \leq B \leq 2 \times 10^{9}$

Ví dụ

Input	Output	Giải thích
4 4 5 17 2 100 0 10 1 200 4	118	ID 2 tự ghép: $2 + 2 = 4 = A$ , được 8 cặp. ID 0 với 4: $0 + 4 = 4 = A$ , được 100 cặp. ID 1 với 4: $1 + 4 = 5 = B$ , được 10 cặp. Tổng: $8 + 100 + 10 = 118$ .
4 4 5 100 0 10 1 100 3 20 4	30	ID 0-4 ( $A$ ): 20 cặp. ID 1-3 ( $A$ ): 10 cặp. Tổng: 30.

Bình luận

Không có bình luận tại thời điểm này.