صبح یک روز تابستانی، مسئول دوره‌ی یکی از المپیادها متوجه شد که ‎$n$‎ سری برگه‌ی تصحیح‌نشده روی دستش مانده و باید این نمرات را تا شب به بچه‌ها اعلام کند‎!‎

پس از مشورت با سایر اعضای کمیته، مسئول دوره دریافت که ‎$m$‎ نفر از دوستانش حاضرند در تصحیح کردن این برگه‌ها به او کمک کنند. می‌دانیم اگر مصحّح ‎$i$‎اُم ‎($1 \le i \le m$)‎ بخواهد برگه‌های سری ‎$j$‎اُم ‎($1 \le j \le n$)‎ را تصحیح کند،$C_{i,j}$‎ ثانیه (‎که عددی مثبت و نه‌لزوماً صحیح است) طول می‌کشد. هم‌چنین هر سری برگه باید تنها توسّط یک مصحّح تصحیح شوند و هیچ مصححی نمی‌تواند در یک لحظه بیش از یک سری برگه‌ی تصحیح نشده در اختیار داشته باشد. از سوی دیگر، پس از اتمام یک سری برگه، مصحّح می‌تواند بلافاصله سری دیگری که هنوز تصحیح نشده را از مسئول دوره گرفته و شروع به تصحیح آن کند.

می‌دانیم مصحّحان در ثانیه صفر (از ابتدای روز) کارشان را شروع می‌کنند و هر مصحّح، پس از اتمام همه‌ی برگه‌های یک سری، نمرات آن را بلافاصله روی تابلو می‌چسباند. با این حال اگر نمرات یک سری برگه در ثانیه ‎$s$‎ از ابتدای روز (‎که عددی مثبت و نه‌لزوماً صحیح است) روی تابلو چسبانده شود، بچه‌ها ‎$s$‎ واحد ناراحت می‌شوند‎!‎

به مسئول دوره کمک کنید و الگوریتمی چندجمله‌ای بر حسب ‎$m$‎ و ‎$n$‎ بدهید که با داشتن تمام ‎$C_{i,j}$‎ها، مشخص کند هر سؤال باید در چه زمانی و توسط کدام مصحّح تصحیح شود تا مجموع ناراحتی‌های بچه‌ها کمینه شود.

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