المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۴:سوال ۸

INOI

برای آماده‌سازی آزمون‌های انتخابی تیم المپیاد کامپیوتر، $n$ کار باقی مانده است که کار شماره‌ی $i$ به $a_i$ دقیقه زمان نیاز دارد. برای افزایش امنیت آزمون‌ها هر کار باید توسط دقیقا یک فرد انجام شود. دنباله‌ی $b_1,b_2,…,b_n$ را برابر با مدت زمان‌هایی در نظر بگیرید که افراد می‌توانند برای انجام کارها صرف کنند. واضح است که اگر کار شماره‌ی $i$ به فرد $j$ داده شود، مقدار $a_i$ باید کم‌تر مساوی $b_j$ باشد. مسئول آزمون‌ها می‌تواند از حداکثر $k$ نفر بخواهد که مدت زمانشان را به چیزی که او می‌گوید، تغییر دهند. دقت کنید که در این تغییرها ممکن است بعضی از $b_i$ ها کاهش یابند.

هدف مسئول آزمون‌ها این است که مقدار زمان‌ها را طوری تغییر دهد به طوری که حداقل یک روش برای نسبت دادن کارها به افراد وجود داشته باشد. در صورت وجود چندین حالت برای این کار، کمینه کردن مجموع $b_i$ها مدنظر او است. برنامه‌ای بنویسید که این مجموع کمینه را در خروجی چاپ کند. در صورتی که امکان انجام همه‌ی کارها وجود نداشته باشد، برنامه‌ باید عدد -۱ را چاپ کند.

ورودی

در سطر اول ورودی دو عدد طبیعی $n$، تعداد کارها و $k$، حداکثر تعداد تغییرها، آمده است.($1\leq n,k \leq 3 \times 10^5 $)

سطر دوم ورودی شامل $n$ عدد طبیعی، $a_1,a_2,…,a_n$ است.( $1\leq a_1,a_2,…,a_n \leq 10^9$)

سطر سوم ورودی شامل $n$ عدد طبیعی، $b_1,b_2,…,b_n$ است.( $1\leq b_1,b_2,…,b_n\leq 10^9$)

خروجی

در تنها سطر خروجی، پاسخ مسئله را چاپ کنید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4 3
10 20 30 40
10 10 10 10
100
4 2
10 20 30 40
10 10 10 10
-1
4 3
10 20 30 40
40 40 40 40
100

ابزار صفحه