Problema B - Comprar máscaras

Há N supermercados na cidade, cada um vende máscaras a preços diferentes. O i-ésimo supermercado vende cada máscara por A_i euros. Precisamos de comprar exatamente M máscaras, mas queremos gastar o mínimo possível.

Parte I

Para controlar o stock de máscaras, cada um dos supermercados decidiu que cada pessoa só pode comprar uma única máscara, ou seja, só podemos comprar uma máscara por supermercado.

Exemplo

Se N = 4, M = 3 e tivermos os seguintes preços:

• A = [1, 2, 1, 3]

Podemos comprar uma máscara de cada um dos primeiros 3 supermercados, por um total de 4 euros.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

Nesta parte os supermercados decidiram aplicar uma estratégia diferente. É permitido comprar um número qualquer de máscaras num único supermercado, mas cada compra aumenta o preço por máscara em um euro. Por isso se um certo supermercado vender máscaras a x euros, após comprarmos uma máscara a segunda máscara custará x + 1 euros, se comprarmos uma segunda a terceira custará x + 2 euros, etc.

Exemplo

Se N = 4, M = 5 e tivermos os seguintes preços:

• A = [1, 2, 1, 3]

A seguinte sequência de compras permite-nos comprar 5 máscaras por 8 euros:

• Comprar do supermercado 1 a 1 euro, novos preços: A = [2, 2, 1, 3]
• Comprar do supermercado 3 a 1 euro, novos preços: A = [2, 2, 2, 3]
• Comprar do supermercado 1 a 2 euros, novos preços: A = [3, 2, 2, 3]
• Comprar do supermercado 2 a 2 euros, novos preços: A = [3, 3, 2, 3]
• Comprar do supermercado 3 a 2 euros, novos preços: A = [3, 3, 3, 3]

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é igual para todas as partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com dois inteiros separados por espaços, primeiro N, representando o número de supermercados, seguido de M, o número de máscaras que pretendemos comprar.

Seguem-se uma linha, contendo N inteiros separados por espaços que representam os preços de uma máscara por supermercado.

Output

O output deve conter uma linha com um inteiro representando o preço mínimo a pagar.

Nota: O resultado pode ser um número superior a 2³², usa o formato de inteiro long long int em C/C++, long em Java e LongInt em Pascal (em Python nada disto é necessário).

Input do Exemplo 1

1
4 3
1 2 1 3

Output do Exemplo 1

4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
4 5
1 2 1 3

Output do Exemplo 2

8

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.