object Main {
	case class Company(members: Int, cost: Int)
	def main(args: Array[String]) {
		val safetyToInt = (x:String) => x.filter("0123456789" contains _).toInt
		val needs, cNum = safetyToInt(readLine())
		val companies = Iterator.continually(readLine()).take(cNum).
			map{_.split(' ').map(safetyToInt)}.
			map{x => Company(members = x(0), cost = x(1))}.toList
 
		def search[T1, T2](f: (Either[T2, T2], T1)=> Either[T2, T2],
				xs: Seq[T1], prev: Either[T2, T2]):Either[T2, T2] = 
			if (xs.headOption.isEmpty) prev
			else f(prev, xs.head) match {
				case l @ Left(_) => search(f, xs.tail, l)
				case r @ Right(_) if xs.tail.nonEmpty =>
					search(f, xs.head +: xs.tail.tail, Left(r.right.get))
				case e @ _ => prev
			}
		case class Cpr(best: Int, mem: Int, cst: Int)
		def compair
		(min: Int)(prev: Either[Cpr, Cpr], crnt: Company): Either[Cpr, Cpr] = {
			val Cpr(best, mem, cst) = prev.left.get
			val next = mem + crnt.members
			val newCost = cst + crnt.cost;
			println(prev);
			(if(next >= min) Right(Cpr(best.min(newCost), mem, cst))
			else Left(Cpr(best, next, newCost)))
		}
 
		val most = companies.map{_.cost}.sum;
		val result =
			companies.tails.foldLeft(Left(Cpr(most, 0, 0)):Either[Cpr, Cpr]){
				(x, y) => search(compair(needs) _, y, Left(Cpr(x.left.get.best, 0, 0)))
			};
		println("result: " + result)
	}
}
 

b2JqZWN0IE1haW4gewoJY2FzZSBjbGFzcyBDb21wYW55KG1lbWJlcnM6IEludCwgY29zdDogSW50KQoJZGVmIG1haW4oYXJnczogQXJyYXlbU3RyaW5nXSkgewoJCXZhbCBzYWZldHlUb0ludCA9ICh4OlN0cmluZykgPT4geC5maWx0ZXIoIjAxMjM0NTY3ODkiIGNvbnRhaW5zIF8pLnRvSW50CgkJdmFsIG5lZWRzLCBjTnVtID0gc2FmZXR5VG9JbnQocmVhZExpbmUoKSkKCQl2YWwgY29tcGFuaWVzID0gSXRlcmF0b3IuY29udGludWFsbHkocmVhZExpbmUoKSkudGFrZShjTnVtKS4KCQkJbWFwe18uc3BsaXQoJyAnKS5tYXAoc2FmZXR5VG9JbnQpfS4KCQkJbWFwe3ggPT4gQ29tcGFueShtZW1iZXJzID0geCgwKSwgY29zdCA9IHgoMSkpfS50b0xpc3QKCgkJZGVmIHNlYXJjaFtUMSwgVDJdKGY6IChFaXRoZXJbVDIsIFQyXSwgVDEpPT4gRWl0aGVyW1QyLCBUMl0sCgkJCQl4czogU2VxW1QxXSwgcHJldjogRWl0aGVyW1QyLCBUMl0pOkVpdGhlcltUMiwgVDJdID0gCgkJCWlmICh4cy5oZWFkT3B0aW9uLmlzRW1wdHkpIHByZXYKCQkJZWxzZSBmKHByZXYsIHhzLmhlYWQpIG1hdGNoIHsKCQkJCWNhc2UgbCBAIExlZnQoXykgPT4gc2VhcmNoKGYsIHhzLnRhaWwsIGwpCgkJCQljYXNlIHIgQCBSaWdodChfKSBpZiB4cy50YWlsLm5vbkVtcHR5ID0+CgkJCQkJc2VhcmNoKGYsIHhzLmhlYWQgKzogeHMudGFpbC50YWlsLCBMZWZ0KHIucmlnaHQuZ2V0KSkKCQkJCWNhc2UgZSBAIF8gPT4gcHJldgoJCQl9CgkJY2FzZSBjbGFzcyBDcHIoYmVzdDogSW50LCBtZW06IEludCwgY3N0OiBJbnQpCgkJZGVmIGNvbXBhaXIKCQkobWluOiBJbnQpKHByZXY6IEVpdGhlcltDcHIsIENwcl0sIGNybnQ6IENvbXBhbnkpOiBFaXRoZXJbQ3ByLCBDcHJdID0gewoJCQl2YWwgQ3ByKGJlc3QsIG1lbSwgY3N0KSA9IHByZXYubGVmdC5nZXQKCQkJdmFsIG5leHQgPSBtZW0gKyBjcm50Lm1lbWJlcnMKCQkJdmFsIG5ld0Nvc3QgPSBjc3QgKyBjcm50LmNvc3Q7CgkJCXByaW50bG4ocHJldik7CgkJCShpZihuZXh0ID49IG1pbikgUmlnaHQoQ3ByKGJlc3QubWluKG5ld0Nvc3QpLCBtZW0sIGNzdCkpCgkJCWVsc2UgTGVmdChDcHIoYmVzdCwgbmV4dCwgbmV3Q29zdCkpKQoJCX0KCgkJdmFsIG1vc3QgPSBjb21wYW5pZXMubWFwe18uY29zdH0uc3VtOwoJCXZhbCByZXN1bHQgPQoJCQljb21wYW5pZXMudGFpbHMuZm9sZExlZnQoTGVmdChDcHIobW9zdCwgMCwgMCkpOkVpdGhlcltDcHIsIENwcl0pewoJCQkJKHgsIHkpID0+IHNlYXJjaChjb21wYWlyKG5lZWRzKSBfLCB5LCBMZWZ0KENwcih4LmxlZnQuZ2V0LmJlc3QsIDAsIDApKSkKCQkJfTsKCQlwcmludGxuKCJyZXN1bHQ6ICIgKyByZXN1bHQpCgl9Cn0K

MjUwIAo1IAozNSAzNjQwIAozMyAyNzA2IAo5OCA5ODEwIAo1NyA1NDcyIAo5NSA3NzkwCg==

250 
5 
35 3640 
33 2706 
98 9810 
57 5472 
95 7790