Tiệm Bánh

Đ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

Bessie điều hành một tiệm bánh với một lò nướng. Lò có thể sản xuất bánh quy trong $t_{C}$ đơn vị thời gian hoặc bánh muffin trong $t_{M}$ đơn vị thời gian. Có $N$ người bạn đến lần lượt, người thứ $i$ đặt $a_{i}$ bánh quy và $b_{i}$ bánh muffin, và sẵn sàng chờ tối đa $c_{i}$ đơn vị thời gian.

Tổng thời gian sản xuất cho một đơn hàng là $a_{i} \cdot t_{C} + b_{i} \cdot t_{M}$ . Bessie có thể dùng "moonies" để giảm thời gian sản xuất: mỗi moonie giảm $t_{C}$ hoặc $t_{M}$ đi 1 đơn vị (nhưng mỗi giá trị tối thiểu phải bằng 1). Việc giảm áp dụng cho tất cả đơn hàng.

Hãy tìm số moonies tối thiểu cần chi để phục vụ tất cả khách hàng trong giới hạn chờ đợi.

Dữ liệu vào

Dòng 1: Số nguyên $T$ ( $1 \leq T \leq 100$ ) — số bộ test.
Mỗi bộ test:
- Dòng đầu (sau dòng trống): Ba số nguyên $N$ , $t_{C}$ , $t_{M}$ ( $1 \leq N \leq 100$ , $1 \leq t_{C}, t_{M} \leq 10^{9}$ ).
- $N$ dòng tiếp theo: Ba số nguyên $a_{i}$ , $b_{i}$ , $c_{i}$ ( $1 \leq a_{i}, b_{i} \leq 10^{9}$ , $a_{i} + b_{i} \leq c_{i} \leq 2 \cdot 10^{18}$ ).

Dữ liệu ra

Với mỗi bộ test, in số moonies tối thiểu trên một dòng.

Ràng buộc

$1 \leq T \leq 100$
$1 \leq N \leq 100$
$1 \leq t_{C}, t_{M} \leq 10^{9}$
$1 \leq a_{i}, b_{i} \leq 10^{9}$
$a_{i} + b_{i} \leq c_{i} \leq 2 \cdot 10^{18}$

Ví dụ

Input	Output	Giải thích
2 3 7 9 4 3 18 2 4 19 1 1 6 5 7 3 5 9 45 5 2 31 6 4 28 4 1 8 5 2 22	11 6	Test 1: Giảm $t_{C}$ từ 7 xuống 2 (5 moonies) và $t_{M}$ từ 9 xuống 3 (6 moonies), tổng 11.

Bình luận

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