#P1226. 你的背包不是背包题

你的背包不是背包题

Background

不要害怕,不难

Description

首先告诉你你有一个体积为V空的背包,和一条路。路上有n个物体标号为1到n,每个物体拥有自己的体积vi你可以选择任意位置作为起点,向n号物体走,所遇物体假如能装进背包就必会被收入囊中,不能的话就跳过继续向前走,问最多能装多少个物体,所占总体积是多少?优先输出物体个数更多的,假如装入物体个数相同,输出总体积更大的结果

Format

Input

第一行为两个整数V和n 第二行为n个整数vi,为第i个物体体积(1≤V≤1e6,1≤n≤1e3,1≤vi≤1e3)

Output

输出两个整数,为最多装物体个数和所占总体积,用空格隔开

Samples

5 6
1 1 2 2 1 3
4 5

Limitation

1s, 1024KiB for each test case.