المضاربة في سوق العقارات عمل مرهق ذو أرباح غير مستقرة. هل سيساعدك الحصول على قرض ضخم من والديك والقدرة على التنبؤ بدقة بأسعار الشقق في أيام محددة؟
تبدأ بدون شقة، لكن رصيدك البنكي هو $10^{100}$. وبما أنك لا تملك رخصة وكيل عقاري، فيجوز لك امتلاك شقة واحدة على الأكثر في كل مرة. لقد حددت بالفعل شقة معينة في موقع جيد، وهي الشقة التي يمكنك شراؤها ثم بيعها، وربما عدة مرات.
نشرت البوابة العقارية MyHouse فترات متوقعة $[a_i, b_i]$ (حيث $a_i < b_i$) لسعر الشقة خلال الأيام الـ $n$ القادمة. سعر الشقة في اليوم $i$ هو عدد حقيقي عشوائي $c_i$ يُختار عشوائياً بانتظام من الفترة $[a_i, b_i]$. بشكل افتراضي، تعرف السعر $c_i$ في بداية اليوم $i$. يجب عليك حينئذٍ أن تقرر ما إذا كنت ستجري صفقة. إذا كنت تمتلك الشقة، يمكنك بيعها مقابل $c_i$، وإذا لم تكن تمتلكها، يمكنك شراؤها مقابل $c_i$.
اليوم فقط (قبل اليوم الأول) تسمح بوابة MyHouse للمستخدمين الجدد بمعرفة الأسعار الدقيقة $c_i$ لمجموعة مختارة من $k$ أيام. أي أنك تختار الآن مجموعة من $k$ أيام وتعرف أسعارها، بينما لكل يوم من الأيام الـ $n - k$ المتبقية ستعرف السعر في بداية ذلك اليوم.
بعد $n$ أيام يجب أن تنتهي بدون شقة؛ ربحك هو الفرق بين رصيدك البنكي النهائي والابتدائي. حدد أقصى قيمة متوقعة* للربح، إذا اخترت المجموعة المكونة من $k$ أيام بشكل أمثل ثم اتخذت قرارات الصفقات بشكل أمثل في كل يوم من الأيام الـ $n$.
*القيمة المتوقعة هي القيمة المتوسطة المرجحة بالاحتمال لمتغير عشوائي. بشكل بديهي، هي النتيجة التي تتوقعها في المتوسط عند تكرار تجربة عشوائية مرات عديدة.
الإدخال
يحتوي السطر الأول على عددين صحيحين $n$ و $k$ ($0 \le k \le n \le 300\,000$؛ $1 \le n$)، ويمثلان على التوالي عدد الأيام وعدد الأسعار التي يمكنك معرفتها فوراً.
تصف الأسطر الـ $n$ التالية فترات الأسعار؛ يحتوي السطر $i$ على عددين صحيحين $a_i$ و $b_i$ ($1 \le a_i < b_i \le 10^6$).
الإخراج
اطبع عدداً حقيقياً واحداً – أقصى قيمة متوقعة ممكنة للربح بعد $n$ أيام.
الخطأ النسبي أو المطلق المقبول هو $10^{-6}$. أي أنه إذا طبعت $x$ وكانت النتيجة الدقيقة الصحيحة هي $y$، فيجب أن يتحقق $|x - y| \le 10^{-6} \cdot \max(1, y)$. يمكنك طباعة ما يصل إلى $20$ رقماً بعد الفاصلة العشرية.
أمثلة
input
4 0 10 30 10 30 40 50 30 60
output
28.75
input
4 1 10 30 10 30 40 50 30 60
output
31.3888888889
input
6 3 10 50 30 70 50 70 30 50 30 40 10 40
output
33.6805555556
ملاحظة
في الاختبار الأول لدينا $k = 0$، لذلك يُعرف كل سعر في بداية يومه. توجد استراتيجية مثلى لشراء الشقة في اليوم $1$ أو $2$ بتكلفة متوقعة قدرها $17.5$، ثم بيعها في اليوم $3$ أو $4$ بدخل متوقع قدره $46.25$. الربح المتوقع هو $46.25 - 17.5 = 28.75$.
في الاختبار الثاني لدينا $k = 1$ ويجب علينا اختيار اليوم $4$ بشكل أمثل، وبذلك نعرف فوراً عدداً حقيقياً $c_4$ من الفترة $[30, 60]$. الربح المتوقع هو $31\frac{7}{18}$ عند اتخاذ قرارات صفقات مثلى.
في الاختبار الثالث الاختيار الأمثل لمجموعة الـ $k$ أيام هو $\{2, 3, 6\}$. نعرف فوراً الأسعار $c_2$ و $c_3$ و $c_6$.