Task DescriptionDiscussion (0)

The input is read from the standard input. The first line contains the two integers

The next

To the standard output, output one integer, which represents the time that the friends

need to cross the bridge.

Task :: z-most

Mr. Little Z went on a trip with several of his friends. However, when they walked through a bewitched forest they ended up at a bewitched bridge. If the total weight of everybody on the bridge is greater than the bridge's capacity, then the bridge teleports everything that is on it to "dimension X". More friends can start crossing the bridge at the same time (as a group), but the next group can only start to cross when the last friend from the previous group has finished crossing the bridge.

Because Mr. Little Z and his friends are in a hurry, they have asked you to

compute the minimum time needed for everyone to cross the bridge.

compute the minimum time needed for everyone to cross the bridge.

Mr. Little Z gave you the following information.

- Capacity of the bridge

- Number of friends

- For every friend

time that the

(1 <=

- Capacity of the bridge

**N**(0 <=**N**<= 400 )- Number of friends

**M**, including Mr. Little Z ( 1 <=**M**<= 16 )- For every friend

**Time**and_{i}**Weight**, two integers that represent the_{i}time that the

**i**-th friend needs to cross the bridge and their weight(1 <=

**Time**,_{i}**Weight**<= 100)._{i}**INPUT:**

The input is read from the standard input. The first line contains the two integers

**N**and

**M**.

The next

**M**lines contain the numbers

**Time**and

_{i}**Weight**.

_{i}**OUTPUT:**

To the standard output, output one integer, which represents the time that the friends

need to cross the bridge.

Input:

Output:

Explanation:

First, friends 2 and 3 go together, and after friend 3 crosses the bridge (after 18 seconds), friend 1 starts crossing.This gives a total of 18 + 24 = 42 seconds.

**100 3**

24 60

10 40

18 50

24 60

10 40

18 50

Output:

**42**

Explanation:

First, friends 2 and 3 go together, and after friend 3 crosses the bridge (after 18 seconds), friend 1 starts crossing.This gives a total of 18 + 24 = 42 seconds.

Submit Solution

Available Languages

Task info

Name: | z-most |

Time: | 1 sec. |

Memory: | 16 MB |

#Tests: | 15 |

Author: | Z |

AddedBy: | admin |

Task Ratings

Difficulty: | 4.4 (17 votes) |

Quality: | 4.4 (15 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

admin | 0.007 s. |

halil | 0.008 s. |

majce | 0.01 s. |

mirosl@v | 0.01 s. |

dejandenib | 0.01 s. |

a70babat | 0.011 s. |

crusader | 0.012 s. |

amirbehshad | 0.013 s. |

aleksa92 | 0.038 s. |

Weramajstor | 0.039 s. |

Solved By