O chefe do almoxarifado de uma pequena empresa deu a seguinte instrução aos seus funcionários: uma caixa só pode ser colocada em cima de uma caixa que contém massa maior ou igual a da caixa a ser empilhada.
As caixas a serem empilhadas tem mesmas dimensões e são fabricadas com mesmo material, de modo que são diferenciadas apenas pelas etiquetas que indicam a massa total armazenada na caixa.
Com a chegada de uma nova remessa de material, os funcionários reservaram o espaço necessário para uma nova pilha de caixas. Um funcionário trazia as caixas do caminhão para a porta do almoxarifado, enquanto um segundo funcionário consultava a etiqueta da caixa recém-chegada: se a massa contida nela permitisse o empilhamento, o funcionário a colocava na pilha; caso contrário, separava a caixa numa sala ao lado.
Sabendo que a pilha pode ter, no máximo, caixas, e conhecida a ordem em que as caixas foram retiradas do caminhão e analisadas, determine a massa total que o funcionário conseguiu empilhar.
A primeira linha da entrada contém os inteiros () e , separados por um espaço em branco.
A linha seguinte contém as massas (), em ordem de retirada, de cada caixa (), separadas por um espaço em branco.
Imprima, em uma linha, a massa total do material contido nas caixas que foram empilhadas.
2 1
10 1510Explicação do exemplo 1: No primeiro caso, a única caixa na pilha é a primeira que é retirada, cuja massa é igual a 10.
10 6
40 25 30 25 20 8 10 2 2 1120Explicação do exemplo 2: No segundo caso, a primeira caixa (40) é selecionada, permitindo que a segunda (25) possa ser colocada sobre ela. A terceira não pode ser empilhada, pois 30 > 25, mas a quarta sim. As duas próximas (20 e 8) também são selecionadas. A sétima não pode ser empilhada (10 > 8), mas a oitava sim, completando o máximo de seis caixas permitidas.