Nước JOI gồm \(N\) bang được đánh số từ \(1\) đến \(N\). Năm 2022, nước này tổ chức bầu cử tổng thống. Việc bỏ phiếu được thực hiện tại từng bang; ứng viên thắng tại một bang sẽ nhận được một phiếu bầu được phân bổ cho bang đó.

Rie là một ứng viên tổng thống. Để giành chiến thắng, cô quyết định đi diễn thuyết tại các bang. Việc diễn thuyết đem lại những kết quả sau:

• Khi tổng thời gian diễn thuyết tại bang \(i\) đạt \(A_i\) giờ, cô nhận được phiếu bầu của bang đó.
• Khi tổng thời gian diễn thuyết tại bang \(i\) đạt \(B_i\) giờ, cô có thêm một cộng tác viên từ bang đó. Cộng tác viên cũng có thể diễn thuyết, giúp tăng tổng thời gian diễn thuyết. Tuy nhiên, một số bang không cung cấp cộng tác viên dù diễn thuyết bao lâu; khi đó, đầu vào cho \(B_i=-1\). Mỗi bang có nhiều nhất một cộng tác viên có thể tham gia.

Cộng tác viên đến từ bang \(i\) có thể diễn thuyết tại bất kỳ bang nào. Trong một bang, nhiều người có thể diễn thuyết đồng thời, và thời gian của tất cả những người đó được cộng lại. Ví dụ, nếu hai người cùng diễn thuyết trong \(x\) giờ, tổng thời gian diễn thuyết tại bang đó tăng \(2x\) giờ. Thời gian diễn thuyết không nhất thiết là số nguyên. Thời gian di chuyển giữa các bang nhỏ đến mức có thể bỏ qua.

Ngày bầu cử đã đến gần, nên Rie muốn nhận được phiếu bầu của \(K\) bang nhanh nhất có thể. Cho thông tin về các bang, hãy tính thời gian ngắn nhất cần thiết để nhận được phiếu bầu của \(K\) bang.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i\) và \(B_i\).

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa thời gian ngắn nhất, tính bằng giờ, để nhận được phiếu bầu của \(K\) bang. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá \(0.01\).

Chỉ được dùng một trong các cách viết sau, không dùng ký hiệu số mũ:

• Số nguyên, chẳng hạn 123, 0, -2022.
• Một số nguyên, dấu chấm . và một dãy chữ số từ 0 đến 9, viết liền nhau không có khoảng trắng. Không giới hạn số chữ số sau dấu chấm thập phân. Ví dụ: 123.4, -123.00, 0.00288.

Các dạng như 1.23456e+05 hoặc 1.23456e5 không được phép.

Ràng buộc

• \(1 \le N \le 500\).
• \(1 \le K \le N\).
• \(1 \le A_i \le 1000\) với mọi \(1 \le i \le N\).
• Với mỗi \(1 \le i \le N\), hoặc \(A_i \le B_i \le 1000\), hoặc \(B_i=-1\).

Phân nhóm

• Nhóm 1 (5 điểm): \(B_i=-1\) với mọi \(1 \le i \le N\).
• Nhóm 2 (5 điểm): \(B_i=-1\) hoặc \(B_i=A_i\) với mọi \(1 \le i \le N\).
• Nhóm 3 (11 điểm): \(N \le 7\).
• Nhóm 4 (12 điểm): \(N \le 20\).
• Nhóm 5 (33 điểm): \(N \le 100\).
• Nhóm 6 (11 điểm): \(K=N\).
• Nhóm 7 (23 điểm): Không có ràng buộc bổ sung.

Ví dụ

3
3
1 5
2 3
4 5

5.500000000000000

7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1

32.000000000000000

5
3
4 -1
5 -1
6 -1
7 7
8 8

11.500000000000000

7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51

62.166666666666664

20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260

644.203571428571422

Nguồn

JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.