Chiến lược học kỳ (Term Strategy)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Peter có $n$ môn và đúng $m$ giờ học. Nếu dành $h$ giờ cho môn $i$, cậu nhận điểm đã cho. Mỗi môn phải được học ít nhất một giờ và điểm của môn đó phải ít nhất $5$. Hãy tối đa hóa tổng điểm.

Input

Dòng đầu chứa $n,m$. Sau đó có $n$ dòng; dòng $i$ chứa $m$ điểm, trong đó phần tử thứ $h$ là điểm nếu học môn $i$ đúng $h$ giờ.

Output

Nếu không có phương án hợp lệ, in câu Peter, you shouldn't have played billiard that much.. Nếu có, in Maximum possible average mark - X.XX..

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

2 4
5 6 7 8
5 7 8 9

Output

Maximum possible average mark - 6.50.

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.