Há N supermercados na cidade, cada um vende máscaras a preços diferentes. O i-ésimo supermercado vende cada máscara por Ai euros. Precisamos de comprar exatamente M máscaras, mas queremos gastar o mínimo possível.
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.
Se N = 4, M = 3 e tivermos os seguintes preços:
Podemos comprar uma máscara de cada um dos primeiros 3 supermercados, por um total de 4 euros.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ M ≤ N ≤ 5 · 104 | Número de supermercados / Máscaras a comprar | |
1 ≤ Ai ≤ 109 | Preços das máscaras |
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
Grupo | Número de Pontos | Restrições adicionais |
---|---|---|
1 | 10 | 1 ≤ N ≤ 100 |
2 | 30 |
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.
Se N = 4, M = 5 e tivermos os seguintes preços:
A seguinte sequência de compras permite-nos comprar 5 máscaras por 8 euros:
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ N ≤ 5 · 104 | Número de supermercados | |
1 ≤ M ≤ 109 | Máscaras a comprar | |
1 ≤ Ai ≤ 109 | Preços das máscaras |
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
Grupo | Número de Pontos | Restrições adicionais |
---|---|---|
3 | 20 | 1 ≤ N ≤ 1 000 e 1 ≤ M ≤ 1 000 |
4 | 40 |
Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:
Grupo | Número de Pontos | Parte | Restrições adicionais |
---|---|---|---|
1 | 10 | Parte I | 1 ≤ N ≤ 1 000 |
2 | 30 | Parte I | |
3 | 20 | Parte II | 1 ≤ N ≤ 1 000 e 1 ≤ M ≤ 1 000 |
4 | 40 | Parte II |
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.
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 232, usa o formato de inteiro long long int em C/C++, long em Java e LongInt em Pascal (em Python nada disto é necessário).
1 4 3 1 2 1 3
4
Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.
2 4 5 1 2 1 3
8
Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.