Trong lúc dạo quanh trên hòn đảo của Khôi Anh, Kiên phát hiện một căn hầm bỏ hoang đầy bí ẩn với vô vàn những viên đá quý lấp lánh. Tuy nhiên, Kiên chỉ mang theo một chiếc túi nhỏ chứa được tối đa \(S\) kg, trong khi căn phòng lại có tới \(n\) viên đá quý với viên thứ \(i\) có khối lượng \(w_i\) kg và có giá trị là \(v_i\) tiền. Vì muốn kiếm tiền nhưng lười biếng, Kiên nhờ bạn hãy giúp anh ấy chọn đá vào túi sao cho mỗi viên đá chỉ được lấy một lần mà đồng thời kiếm được nhiều lợi nhuận nhất.

Input

• Dòng đầu gồm 3 số \(subtask\_id, n, S\) là số thứ tự của subtask, số viên đá trong phòng và tải trọng tối đa của túi (\(1 \le subtask\_id \le 3\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm một cặp số \((w_i, v_i)\) biểu thị khối lượng và giá trị của từng viên đá.

Output

• In ra một số thực là số tiền tối đa có thể kiếm được, làm tròn đến 6 chữ số sau dấu phẩy.

Constraints

• Subtask 1 (20% số điểm): \(n, S, w_i, v_i\) là các số nguyên. \(1 \le n \le 100, 0 \le S \le 10^5, 1 \le w_i, v_i \le 10^9\).
• Subtask 2 (40% số điểm): \(n\) là số nguyên. \(S, w_i, v_i\) là các số thực. \(1 \le n \le 100, 0 \le S \le 10^5, 1 \le w_i, v_i \le 10^9\). Tuy nhiên, trong \(n\) giá trị là số thực \(w_i\), luôn tồn tại \(n - 1\) giá trị \(w_i\) là số nguyên. Các số thực có tối đa 6 chữ số thập phân sau dấu phẩy.
• Subtask 3 (40% số điểm): \(n\) là số nguyên. \(S, w_i, v_i\) là số thực. \(1 \le n \le 36, 0 \le S \le 10^{18}, 1 \le w_i, v_i \le 10^9\). Các số thực có tối đa 6 chữ số thập phân sau dấu phẩy.

Example

1 5 67
67 90
40 61
26 41
66 101
6 7

102.000000