Dərs cədvəli#2645
Fred Hackerin məktəbində C \times T dərs var və bunlar kateqoriyaya bölünüb, hər kateqoriya üzrə dərs mövcuddur. Gün başlanğıcda bütün -ci kateqoriyadan olan dərslərin eyni vaxtda keçirilməsi ilə başlayır. Bunlar eyni anda bitir, sonra bütün -ci kateqoriyanın dərsləri keçirilir və s. Fred hər kateqoriyadan məhz bir dərs seçməlidir. Onun məqsədi gündəlik cədvəli üzrə tələb olunan ümumi "enerji" miqdarını minimallaşdırmaqdır.
Bir cədvəlin enerjisi seçilən dərslərə lazım olan enerji və bir dərsdən digərinə getmək üçün sərf olunan enerjilərin cəminə bərabərdir.
-ci kateqoriyada -ci dərsi seçmək e_{ij} ədəd enerji tələb edir. Sinif otaqları dəhliz boyunca tam ədədlərlə nömrələnmiş yerlərdə yerləşir (nömrələr -dan -ə qədərdir). -ci kateqoriyada -ci dərs p_{ij} yerində keçirilir. Fred mövqeyindən başlayır, seçdiyi sinif otaqlarını ardıcıllıqla ziyarət edir və sonda mövqeyində bitir. Gedilən məsafə olarsa, o qədər xidməti enerji sərf olunur.
Birinci sətirdə (z \leq 20) — testlərin sayı verilir. Hər testdə 3 ədəd tam ədəd: , , və (1 \leq c \leq 25, 1 \leq t \leq 1000, 1 \leq l \leq 1\,000\,000) verilir. Növbəti c \times t sətirdə hər dərsin yeri və enerji sərfi göstərilib. İlk sətir -ci kateqoriyaya, sonra sətir -ci kateqoriyaya və s. aiddir. Eyni kateqoriyada heç iki dərs eyni yerdə keçirilmir. Zəmanət verilir ki, 1 \leq e_{ij} \leq 1\,000\,000 və 0 \leq p_{ij} \leq l.
Nümunə girişi üçün izah
Fred gün ərzində dərs seçməlidir və hər bir dərs üçün seçim var. Dəhlizin uzunluğu -dir. Fredin birinci mümkün dərsi otaq -dədir və hər gün üçün vahid enerji tələb edir və s.
Hər test üçün cavabı ayrıca sətirdə yazın — tələblərə uyğun mümkün ən az enerji sərfi olan cədvəlin minimal enerjisini çap edin.
Nümunə 1