题目背景

小明在一家网红奶茶店打工。店里有一款招牌奶茶，要求必须调制出恰好 V 毫升的基底液。

店里有 N 种不同的糖浆（每种糖浆都有无数瓶）。第 i 种糖浆每次按压会挤出 v_i 毫升的液体，并且含有 t_i 大卡的卡路里。

现在讲究健康饮食，店长要求小明在恰好凑齐 V 毫升的前提下，使得这杯奶茶的总卡路里最低。同时，为了减轻店员的工作量，如果在卡路里一样低的情况下，要求按压糖浆的总次数最少。

题目描述

给定目标体积 V 和 N 种糖浆，每种糖浆的数量无限。求恰好凑出 V 毫升的最低总卡路里，若有多解则输出按压次数最少的方案。

输入格式

第一行包含两个整数 V 和 N，分别表示目标体积和糖浆种类数。

接下来 N 行，每行两个整数 v_i 和 t_i，分别表示第 i 种糖浆单次按压的体积和卡路里。

输出格式

输出两个整数，用空格隔开，分别表示最低的总卡路里和最少的按压总次数。

如果无论如何也无法恰好凑出 V 毫升，请输出 -1 -1。

样例输入

20 3
5 10
10 20
4 9

样例输出

40 2

样例解释 方案一：按 4 次第 1 种糖浆，体积 4 × 5 = 20，卡路里 4 × 10 = 40，按压 4 次。 方案二：按 2 次第 2 种糖浆，体积 2 × 10 = 20，卡路里 2 × 20 = 40，按压 2 次。 方案三：按 5 次第 3 种糖浆，体积 5 × 4 = 20，卡路里 5 × 9 = 45。 最低卡路里是 40，在卡路里同为 40 的方案中，方案二按压次数（2次）更少，故输出 40 2。

数据范围

1 ≤ V ≤ 10000，1 ≤ N ≤ 100，1 ≤ v_i, t_i ≤ 1000。