Bob Roberts 喜欢在开车时听音乐，但他拥有的汽车有些老旧。车里没有蓝牙或 USB 连接功能，但好在他有一个 CD 播放器，所以他一直在把许多音乐转录到 CD 上。目前他只剩下两张 CD，并希望尽可能多地将剩余的音乐存入这两张 CD 中。给定 CD 的容量和歌曲集合，你能帮他找出他能存入这两张 CD 的音乐总时长（以分钟为单位）的最大值吗？

输入格式

输入的第一行包含两个整数 $c$ 和 $n$，其中 $c$ ($1 \le c \le 1\,000$) 是每张 CD 可以容纳的音乐时长（分钟），$n$ ($1 \le n \le 1\,000$) 是可供选择的歌曲数量。接下来的一行包含 $n$ 个正整数，表示每首歌的长度（分钟）。没有任何一首歌的长度会超过 $1\,000$ 分钟。

输出格式

输出两张 CD 上各自存储的音乐时长（分钟），要求使 Bob 能存入两张 CD 的音乐总时长最大化。首先显示装得较满的那张 CD 的时长。如果存在多种方案总时长相同，则选择两张 CD 时长差值最小的那种方案。

样例

样例输入 1

100 5
10 20 40 60 85

样例输出 1

100 95

样例输入 2

100 5
10 20 30 40 50

样例输出 2

80 70