Ông JOI điều hành khách sạn IOI trên cao nguyên IOI, một địa điểm trượt tuyết nổi tiếng. Địa hình phức tạp ở đây rất được những người trượt tuyết giỏi yêu thích, nhưng lại không thân thiện với người mới bắt đầu. Ông JOI muốn tìm tuyến trượt dễ nhất để giới thiệu cao nguyên cho những người mới tập.

Tuyến trượt dễ nhất là tuyến có vận tốc trung bình nhỏ nhất. Vận tốc trung bình của cả tuyến bằng tổng quãng đường chia cho tổng thời gian đi hết tuyến. Điểm bắt đầu phải là một địa điểm có thể đến bằng cáp treo đi thẳng từ khách sạn IOI; điểm kết thúc phải là khách sạn IOI.

Các địa điểm được đánh số từ \(1\) đến \(n\), trong đó khách sạn IOI ở địa điểm \(n\). Địa điểm càng cao thì có số hiệu càng nhỏ; không có hai địa điểm cùng độ cao. Mỗi đoạn đường chỉ đi từ nơi cao xuống nơi thấp, nên không thể đi rồi quay lại cùng một địa điểm.

Yêu cầu

Cho các đoạn đường có thể dùng để trượt tuyết, chiều dài và vận tốc trung bình trên từng đoạn, cùng các địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn, hãy tìm vận tốc trung bình nhỏ nhất của một tuyến trượt hợp lệ. Làm tròn kết quả đến số nguyên gần nhất, với phần thập phân từ \(0{,}5\) trở lên được làm tròn lên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(n,m,c\): số địa điểm, số địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn và số đoạn đường có thể dùng.
• Dòng thứ hai chứa \(m\) số nguyên \(a_1,a_2,\ldots,a_m\), là các địa điểm có thể đến bằng cáp treo trực tiếp từ khách sạn.
• Trong \(c\) dòng tiếp theo, dòng thứ \(j\) chứa bốn số nguyên \(f_j,t_j,d_j,s_j\): điểm đầu, điểm cuối, chiều dài và vận tốc trung bình của đoạn đường thứ \(j\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là vận tốc trung bình nhỏ nhất sau khi làm tròn.

Ràng buộc

• \(1\le n\le10\,000\), \(1\le m<n\), \(1\le c\le100\,000\).
• \(1\le a_i<n\) với \(1\le i\le m\).
• \(1\le f_j<t_j\le n\), \(1\le d_j\le100\), \(1\le s_j\le100\,000\) với \(1\le j\le c\).
• Luôn tồn tại ít nhất một tuyến bắt đầu tại một địa điểm có cáp treo trực tiếp từ khách sạn và kết thúc tại khách sạn.
• Mọi giá trị sai lệch không quá \(0{,}01\) so với vận tốc trung bình nhỏ nhất đều cho cùng một số nguyên khi làm tròn theo quy tắc trên.
• Giới hạn thời gian: \(1\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(20\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 20. Mỗi nhóm được \(5\) điểm nếu trả lời đúng, tổng cộng \(100\) điểm.

• Các test tương ứng với \(20\%\) tổng số điểm thỏa mãn \(n\le10\) và \(c\le100\).
• Các test tương ứng với \(50\%\) tổng số điểm thỏa mãn \(n\le100\) và \(c\le100\).

Các bảo đảm trên có thể bao hàm nhau, không phải các phân nhóm điểm tách biệt để cộng lại.

Ví dụ

3 1 3
1
1 2 6 1000
2 3 4 2000
1 3 3 3000

1250

4 2 5
1 2
1 3 2 5000
1 3 9 4000
2 3 3 5000
2 4 4 7000
3 4 8 3000

3261