H. Канистра побольше

Как классная задача H, но канистра вмещает $k$ баков, а не один.

В городе можно купить сразу несколько баков бензина: один заливается в бак, остальные — в канистру, и в канистре не может оказаться больше $k$ баков. Каждый купленный бак стоит $c_i$. Переливание из канистры в бак по-прежнему бесплатно.

Состояние — пара «город и сколько баков в канистре», то есть $(n) \times (k + 1)$ вершин. Переходы из $(i, j)$ по дороге в город $t$:

• если $j \ge 1$: перелить и ехать — цена $0$, попадаем в $(t, j - 1)$;
• купить $q$ баков, где $1 \le q \le k + 1 - j$: цена $q \cdot c_i$, попадаем в $(t, j + q - 1)$.

При $k = 1$ это ровно классная задача — полезно проверить себя на её примере.

Обратите внимание, что покупать больше, чем помещается, бессмысленно, а покупать бак, когда канистра не пуста, — иногда осмысленно: бензин в дешёвом городе лучше дорогого впереди.

Первая строка содержит числа $n$ ($1 \le n \le 100$) и $k$ ($1 \le k \le 5$).

Вторая строка — $n$ чисел $c_i$ ($0 \le c_i \le 100$).

Третья строка — число дорог $M$, далее $M$ строк с парами городов. Дороги двусторонние, между парой городов не более одной дороги, петель нет.

Одно число — наименьшая суммарная стоимость или $-1$.