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

در یک کرخانه‌ی چو‌ب‌بری عجیب برای این‌که یک تکه چوب را در یک مرحله به $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$ ام استفاده شده است.


 

===== محدودیت‌ها =====


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

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

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 \\ 1 \\ 5 \\ 10 | 3 \\ 3 0 0 |
</WRAP>


<پاسخ>



</پاسخ>


  * [[سوال ۲|سوال بعد]]