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~ (~1 \le subtask\_id \le 3~), ~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.

• 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.

Scoring

Sample Input 1

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

Sample Output 1

102.000000

Notes

Chọn viên đá quý thứ 2 và thứ 3, tổng cân nặng là 66 và tổng giá trị là 102.