Optimal Yarış Sistemi#10677

Optimal Yarış Sistemi

1 saniyə

128 meqabayt

Çox çətin

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.

Tutaq ki, siz $N$ həll göndərmisiniz və bu həllər $1$ -dən $N$ -ə qədər unikal ədədlərlə nömrələnib. Sistem həlləri qruplar şəklində yoxlayır. Ardıcıl nömrələrə sahib həllər bir və ya bir neçə qrupa bölünə bilər və sistem bu qrupları ardıcıllıqla, birincidən başlayaraq yoxlayır. Yoxlama prosesi $0$ -cı saniyədən başlayır. Əvvəlcə sistem ilk qrupdakı bütün həlləri yoxlayır və müəlliflər bu qrupun nəticələrini eyni anda və dərhal öyrənirlər. Sonrakı qrup varsa, o da yoxlanılır və nəticələr eyni qaydayla açıqlanır. Bu proses bütün həllər yoxlanana və nəticələr məlum olana qədər davam edir.

Hər bir $i$ -ci həllin yoxlanmasına $T_{i}$ T_i saniyə sərf olunur və müəllifin narahatlıq dərəcəsi $C_{i}$ C_i-dir. Hər bir qrupu yoxlamazdan əvvəl sistemin konfiqurasiyası üçün $K$ saniyə lazımdır. Bütün $T_{i}$ T_i, $C_{i}$ C_i və $K$ tam ədədlərdir.

Məsələn, əgər $i, i + 1, \dots, i + j$ i, i + 1, \ldots, i + j nömrəli həllər bir qrup kimi $Z$ saniyəsində yoxlanmağa başlasa, bu qrupun nəticələri $Z + K + (T_{i} + T_{i + 1} + \dots + T_{i + j})$ Z + K + (T_i + T_{i + 1} + \ldots + T_{i + j}) saniyəsində məlum olacaq. Qeyd edək ki, müəlliflər nəticələri eyni anda və dərhal öyrənirlər.

Əgər $i$ -ci həllin nəticəsi $P_{i}$ P_i-ci saniyədə məlum olarsa, müəllifin narahatlığı $C_{i} \times P_{i}$ C_i \times P_i qədər artır. Məqsəd bütün iştirakçılar üzrə ümumi narahatlığı minimuma endirməkdir.

Giriş

İlk sətr $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100) — testlərin sayını göstərir. Hər test üçün iki ədəd verilir: $N$ ( $1 \leq N \leq 2 \times 1 0^{5}$ 1 \leq N \leq 2\times 10^{5}), ( $\sum N \leq 2 \times 1 0^{5}$ \sum N \leq 2\times 10^{5}) və $K$ ( $0 \leq K \leq 50$ 0 \leq K \leq 50) — həllərin sayı və sistemin konfiqurasiya müddəti. Sonra $N$ sətir gəlir, hər biri iki tam ədəd $T_{i}$ T_i ( $1 \leq T_{i} \leq 100$ 1 \leq T_i \leq 100) və $C_{i}$ C_i ( $1 \leq C_{i} \leq 100$ 1 \leq C_i \leq 100) — $i$ -ci həllin yoxlanılma vaxtı və müəllifin narahatlıq dərəcəsi.

Çıxış

Hər test üçün mümkün olan ən az ümumi narahatlıq dərəcəsini çap edin. Hər cavab yeni sətrdə verilməlidir.

Nümunələr

Nümunə 1

Qeyd

Bir test ( $t = 1$ t=1) vəziyyətini nəzərdən keçirin: $N = 5$ N=5, $K = 1$ K=1 saniyə sistem konfiqurasiyasına sərf olunur. $(T_{1}, T_{2}, T_{3}, T_{4}, T_{5}) = (1, 3, 4, 2, 1)$ (T_1, T_2, T_3, T_4, T_5) = (1, 3, 4, 2, 1) və $(C_{1}, C_{2}, C_{3}, C_{4}, C_{5}) = (3, 2, 3, 3, 4)$ (C_1, C_2, C_3, C_4, C_5) = (3, 2, 3, 3, 4)-dür. Həlləri $3$ qrupa bölək: $1, 2, 3, 4, 5$ {1, 2}, {3}, {4, 5}.

Bu halda, nəticələr $(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}) = (5, 5, 10, 14, 14)$ (P_1, P_2, P_3, P_4, P_5) = (5, 5, 10, 14, 14) saniyələrində məlum olur. Hər müəllifin narahatlığı $(15, 10, 30, 42, 56)$ (15, 10, 30, 42, 56) olur. Ümumi narahatlıq $15 + 10 + 30 + 42 + 56 = 153$ 15 + 10 + 30 + 42 + 56 = 153-dür. Bu misalda daha az ümumi narahatlıq əldə etmək mümkün deyil.

Bal hesablama

Bu məsələ $8$ alt tapşırıqdan ibarətdir: