[POI2004]PRZ

一支登山队在爬山时遭遇了雪崩。逃生途中，他们需要通过一座年久失修的桥。由于桥的承重能力有限，队员们必须分批过桥：只有当前一批队员全部通过后，下一批队员才能开始过桥。

每名队员都有各自的过桥时间和重量。每一批队员的总重量不能超过桥的最大承重量，该批队员的过桥时间等于其中过桥最慢的队员所需的时间。

请合理安排队员的分组方案，使所有队员通过桥的总时间最短。

输入格式

第一行包含两个整数 $W$ 和 $n$ ，分别表示桥的最大承重量和队员总数。

接下来 $n$ 行，每行包含两个整数 $t$ 和 $w$ ，分别表示一名队员过桥所需的时间和该队员的重量。

输出一个整数，表示所有队员通过桥所需的最短总时间。

本题为 POI 2004 试题「PRZ」，题面与测试数据整理自 BZOJ 2073。