Gần đây, Nông dân John đã mua một trang trại mới để mở rộng đế chế sản xuất sữa của mình. Trang trại mới được nối với một thị trấn gần đó bằng một mạng lưới đường ống, và FJ muốn tìm ra tập hợp đường ống tốt nhất để mua nhằm bơm sữa từ trang trại đến thị trấn.

Mạng lưới đường ống được mô tả bởi \(N\) điểm nối (các đầu mút của đường ống), được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 1000\)). Điểm nối 1 biểu thị trang trại của FJ và điểm nối \(N\) là thị trấn. Có \(M\) đường ống hai chiều (\(1 \leq M \leq 1000\)), mỗi đường ống nối một cặp điểm nối. Đường ống thứ \(i\) có giá \(c_i\) đô la để FJ mua sử dụng và có thể hỗ trợ lưu lượng \(f_i\) lít sữa mỗi giây.

FJ chỉ muốn mua các đường ống thuộc một đường đi có hai đầu mút là các điểm nối 1 và \(N\). Chi phí của đường đi là tổng chi phí của các đường ống trên đường đi. Lưu lượng trên đường đi là giá trị nhỏ nhất trong các lưu lượng của những đường ống trên đường đi (vì đây là nút thắt cổ chai đối với dòng chảy dọc đường đi). FJ muốn tối đa hóa lưu lượng của đường đi chia cho chi phí của đường đi. Đề bài đảm bảo tồn tại một đường đi từ \(1\) đến \(N\).

Phân nhóm

• Các test 2–5 thỏa mãn \(N,M \leq 100\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường ống bằng bốn số nguyên: \(a\) và \(b\) (hai điểm nối khác nhau được đường ống nối lại), \(c\) (chi phí của đường ống) và \(f\) (lưu lượng của đường ống). Chi phí và lưu lượng đều là các số nguyên dương trong phạm vi \(1 \ldots 1000\).

Dữ liệu ra

In \(10^6\) lần giá trị tối ưu, cắt bỏ phần thập phân để thu được một số nguyên (tức là làm tròn xuống số nguyên thấp hơn liền kề nếu giá trị này không phải là số nguyên).

Ví dụ

3 2
2 1 2 4
2 3 5 3

428571

Nguồn

USACO 2019 December Contest, Gold - Milk Pumping: https://usaco.org/index.php?page=viewproblem2&cpid=969

Tác giả: Brian Dean.