کارخانه‌ی چوب‌بری عجیب

در یک کرخانه‌ی چو‌ب‌بری عجیب برای این‌که‌یک تکه چوب را در یک مرحله به $k$ تکه برش بزنند $(2 \leq k \leq n)$ (یعنی $k-1$ بار برش بخورد) $c_k$ واحد پول گرفته می‌شود. می‌خواهیم یک تکه چوب را با کم‌ترین خرج دقیقا $n$ قسمت کنیم.

در خط اول ورودی عدد $n$ ($1 \leq n \leq 5000$) و در $n-1$ خط بعدی در هر خط یک عدد آمده که سطر $i$ ام، عدد $c_i$ است.

در فایل خروجی در خط اول کم‌ترین میزان خرج را بنویسید. در خط بعدی $n-1$ عدد بنویسید که عدد $i$ ام این خط تعداد بارهایی است که از عمل $i+1$ ام استفاده شده است.

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