Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Rules
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
XI Olympiad in Informatics 2003/2004

Task: prz

Passage

II stage competition  
Source file: prz.xxx (xxx=pas,c,cpp)
Memory Limit: 32 MB

A team of Byteholers has set out on a trip into Bytemountains. Unfortunately they have caused an avalanche and now have to escape it. There is an old cable-bridge over a chasm ahead of them. They have to cross the bridge as quickly as possible. The Byteholers are intimate friends and therefore have decided that either all or none of them shall survive.

The bridge is old and worn-out, so it won't withstand a great weight. The total weight of Byteholers on the bridge at any time cannot exceed some limit. Furthermore it is a cable-bridge, so the Byteholers have to cross it in groups. Next group may enter it only after the previous one has left.

It is known how much time each Byteholer needs to cross the bridge. A crossing time of a group is the crossing time of the slowest member of the group. Total crossing time of all Byteholers is the sum of crossing times of all groups. Obviously it depends on the manner in which they split into groups.

Be their saviour! Calculate the minimal crossing time of all the Byteholers.

Task

Write a programme that:

  • reads the description of the bridge and Byteholers from standard input,
  • determines the minimal total crossing time of all Byteholers,
  • writes the determined time to the standard output.

Input

The first line of the standard input contains two integers separated by a single space: w - defining the maximal weight allowed for the bridge (100 <= w <= 400) and n - the number of Byteholers (1 <= n <= 16). In each of the following n lines there are two integers separated by a single space, describing successive Byteholers: t - the time needed by the Byteholer to cross the bridge (1 <= t <= 50) and w - the weight of the Byteholer (10 <= w <= 100).

Output

Your programme should write a single integer in the first and only output line. The integer should denote the minimal total crossing time of all Byteholers.

Example

For the following input data:

100 3
24 60
10 40
18 50

the correct answer is:

42



Print friendly version