Ba Lô Phân Số

Cho $N$ vật. Vật thứ $i$ có khối lượng $w_i$ và giá trị $v_i$. Bạn có một ba lô sức chứa $W$.

Khác với ba lô 0/1, ở đây bạn được cắt vật: có thể lấy một phần bất kỳ của một vật (ví dụ $0.3$ của vật $i$), khi đó khối lượng và giá trị cũng giảm theo tỉ lệ. Hãy tìm tổng giá trị lớn nhất nhét vào ba lô.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$.

Dữ liệu ra

In ra tổng giá trị lớn nhất, với độ chính xác ${10}^{-4}$.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le W\le {10}^9$
• $1\le w_i\le {10}^6$
• $1\le v_i\le {10}^9$

Ví dụ

Ghi chú

Bài này khác biệt với ba lô 0/1 ở chỗ có thể lấy phân số — giải được bằng tham lam theo tỷ số $v_i/w_i$.