Optimal Yarış Sistemi

Soyuq zarafatlar hər zaman uğurlu olmur, lakin bu gün göndərilmiş bütün həllərin yarış ərzində deyil, yarış bitdikdən sonra yoxlanılması planlaşdırılır. $N$ sayda həll göndərildiyini fərz edək və bu həlləri $1$ ilə $N$ arasında tam ədədlərlə nömrələyək. Belə ki, sistemdə $1,2,....,N$ nömrəli həllər var. Sistem həlləri qruplar şəklində yoxlayır. Həllər ardıcıl nömrələrdən ibarət bir və ya bir neçə qrupa parçalana bilər və sistem bu qrupları birincidən başlayaraq bir-bir sıra ilə yoxlayır. Yoxlama prosesi $0$ zamanından başlayır. Əvvəlcə birinci qrupdakı bütün həllər yoxlanılır və sonra bu qrupdakı həllərin hamısının nəticələri eyni anda iştirakçılara bəlli olur. Daha sonra əgər ikinci qrup varsa, eyni qayda ilə həmin qrupdakı həllər yoxlanılır və nəticələri bəlli olur və s. bu şəkildə bütün həllər yoxlanılır və nəticələr iştirakçılara bəlli olur.

$i$-ci həllin sistem tərəfindən yoxlanılmasına sərf olunan zaman $T_i$ və həmin həllin sahibinin, həllin nəticəsini səbirsizliklə gözləmə dərəcəsi $C_i$ öncədən bilinir. Eyni zamanda sistemin hər bir qrupu yoxlamazdan əvvəl yenidən konfiqurasiya edilməsi lazımdır və buna sərf olunan zaman $K$-dır. $T_i$, $C_i$ və $K$ tam ədədlərdir.

Misal üçün, əgər $i,i+1,....,i+j$ nömrəli həllər qrup şəklində yoxlanılarsa və bu qrupun yoxlanılması $Z$ zamanında başlayarsa, həmin qrupdakı hər bir həllin nəticəsi $Z+K+(T_i+T_{i+1}+.....+T_{i+j}$) zamanında bəlli olacaq. Bir daha qeyd edək ki, qrupdakı bütün həllərin nəticəsi eyni anda bəlli olur. Əgər $i$-ci həllin nəticəsi $P_i$ zamanında bəlli olarsa, həmin həllin sahibinin narahatlığı $C_i\ast P_i$ qədər artır. İştirakçıların narahatlığı nə qədər az olarsa, bu sistemin bir o qədər optimal olması deməkdir.

Siz verilənlər əsasında iştirakçıların toplam narahatlığının mümkün minimum qiymətini müəyyən etməlisiniz.

Nümunələr