Liftlər
Viti yeni seyfini göydələnin N-ci mərtəbəsindəki ofisinə qaldırmaq üçün yenidən yükdaşıyıcıların köməyindən istifadə etməlidir. Lakin bu dəfə ödəniş sistemi dəyişib. İndi pilləkənlə bir mərtəbə yuxarı qalxmaq U manat, bir mərtəbə aşağı enmək D manat, liftdən istifadə etmək I manat və liftdən çıxmaq J manat başa gəlir.
Ofisdə yalnız müəyyən mərtəbələrdə dayanan L lift var.
Vitiyə seyfi birinci mərtəbədən ən az xərclə qaldırmaq üçün marşrut hazırlamaqda kömək edin.
Giriş verilənləri
Giriş faylının birinci sətirində tam ədədlər N, U, D, I, J, L verilir. Sonrakı L sətirin hər biri müvafiq liftin təsvirini verir. Hər biri K_i ədədi ilə başlayır — i-ci liftin dayandığı mərtəbələrin sayı, sonra isə K_i təbii ədədlər gəlir — bu liftin dayandığı mərtəbələr (hər bir lift üçün mərtəbələr artan ardıcıllıqla verilir). 0 ≤ U ≤ 1000, 0 ≤ D ≤ 1000, 0 ≤ I ≤ 1000, 0 ≤ J ≤ 1000, 0 ≤ L ≤ 500, 1 ≤ N ≤ 1000000, 2 ≤ K_i ≤ 1000, K_1+K_2+…+K_L ≤ 1000. Göydələndə mərtəbələrin sayı 1000000-dan çox deyil.
Çıxış verilənləri
Çıxış faylında bir ədəd — seyfin qaldırılmasının minimal dəyərini göstərin.