یک جاده‌ی کاملا صاف و مستقیم که در مکان‌هایی از آن لامپ روشنایی نصب شده را در نظر بگیرید. لامپ‌ها دارای ارتفاع‌های مختلف می‌باشند. روی لامپ‌ها به سمت جاده بوده و تمام لامپ‌ها (در صورت روشن بودن) یک زاویه‌ی ‎۹۰‎ درجه را روشن می‌کنند.

از آن‌جایی که این جاده در منطقه‌ای کوهستانی قرار دارد، اگر در یک شب برفی لامپی را روشن کنیم، به علت وجود برف تمام منطقه‌ای که نور از آن عبور می‌کند را به طرز زیبایی روشن می‌شود. یعنی اگر صفحه‌ای عمودی را در نظر بگیریم که زمین را در مسیر جاده قطع می‌کند، مساحت روشن شده از نور هر لامپ یک مثلث قائم‌الزاویه‌ی متساوی‌الساقین خواهد بود که موقعیت راس آن منطبق بر لامپ و وتر آن روی جاده قرار دارد. می‌خواهیم حد اکثر ‎$k$‎ لامپ را روشن کنیم که مساحتی از این صفحه فرضی که درون مثلث‌های روشن قرار می‌گیرد، بیشینه شود.

• سطر اول ورودی شامل عدد ‎$n$‎ و ‎$k$‎ به ترتیب و با یک فاصله می‌باشد.
• در هر یک از ‎$n$‎ سطر بعدی دو عدد نامنفی ‎$x_i$‎ و ‎$h_i$‎ به ترتیب و با یک فاصله آمده‌است. ‎$x_i$‎ فاصله‌ی پایه‌ی لامپ ‎$i$،‎ام از وسط جاده و ‎$h_i$‎ ارتفاع لامپ از سطح جاده است. (جاده بسیار طولانی است و نور تمام لامپ‌ها درون جاده قرار می‌گیرد.)‎
• ‎$1\leq n \leq 300$‎ و ‎$0\leq h_i,x_i \leq 30000$‎

• در سطر اول خروجی مقدار بیشینه‌ی مساحتی از فضا را که می‌توان روشن کرد بنویسید.
• در سطر بعدی شماره‌ی لامپ‌هایی که باید روشن شوند را به ترتیب صعودی بنویسید. شماره‌گذاری لامپ‌ها از ‎۱‎ شروع می‌شود

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل