Estratégia de Pneus — Série B
A MFP Racing Série B é a liga de acesso à elite do automobilismo da MFP. Diferente da categoria principal, as equipes têm orçamento mais limitado e não podem reaproveitar pneus entre stints — cada conjunto de pneus só pode ser usado uma vez por corrida. A equipe preparou exatamente 5 conjuntos numerados de $1$ a $5$ para a pilota, cada um com características únicas:
- $t_i$: tempo por volta (em segundos) com o conjunto $i$.
- $d_i$: número máximo de voltas consecutivas que o conjunto $i$ aguenta antes de precisar ser substituído obrigatoriamente.
A pilota pode usar cada conjunto no máximo uma vez. Cada pit-stop (troca de pneu) adiciona $P$ segundos e há no máximo $S$ trocas disponíveis. A corrida tem $N$ voltas.
Determine o menor tempo total (em segundos) para completar as $N$ voltas.
Input
A primeira linha contém três inteiros $N$, $P$ e $S$ $(1 \le N \le 4000,\ 1 \le P \le 500,\ 0 \le S \le 4)$.
As próximas $5$ linhas descrevem os pares de botas. A $i$-ésima dessas linhas contém $t_i$ e $d_i$ $(1 \le t_i \le 300,\ 1 \le d_i \le N)$.
Output
Um único inteiro: o menor tempo total em minutos. É garantido que sempre existe pelo menos uma estratégia válida para completar os $N$ quilômetros.
10 20 2 80 4 83 6 90 7 70 2 95 10
832
Explanation 1:
Estratégia ótima: par 1 por 4 km (4×80 = 320 min) + troca (20 min) + par 2 por 6 km (6×83 = 498 min) = **838 min**.
10 20 0 80 4 83 6 90 7 70 2 95 10
950
10 20 4 80 4 83 6 90 7 70 2 95 10
832
1 50 0 5 1 10 2 3 1 7 1 9 1
3