Задача 9a. Задача за раницата

Дадена е раница с вместимост M килограма и N вида предмети, като всеки вид се характеризира с две числа - тегло m_i и стойност c_i. Да се избере такова множество от предмети, чиято стойност е максимална, а сумата от теглата не надвишава M. Разполагаме с неограничен брой предменти от всеки вид.

Вход
На стандартния вход се четат две цели числа M и N (не по-големи от 100). На следващия ред са теглата на видовете предмети, а на третия ред са стойностите на предметите от всеки вид.

Изход
На стандартния изход се отпечатва решението на задачата - N числа, като всяко число е брой предмети от съответния вид.

Задача 9b.  Пътищата към нулата

    Един ден президентът на Галактиката Зейфод Бийблброкс попадна в целочислената решетка на едно тъпо тримерно пространство след случайно телепортиране, наложило се поради неминуемия сблъсък на кораба на Зейфод с една малка планета. И добре, че се намираше в положителния октант, защото единствения начин да се излезе оттам  беше през нулата на пространството, като единственото нещо, което можеше  да прави беше да отиде в целочислена точка, чиято сума от координати е с единица по-малка от сумата на координатите на точката, в която се намираше в момента. И то използвайки двата си крака и трите си ръце! Положението се усложняваше и от факта, че двете му глави не можеха да стигнат до споразумение в кой момент коя координата на бъде намалена с единица, за да бъде определена точката на скока.  В резултат движенията на Зейфод Бийблброкс бяха направлявани един път от първата глава, и после от втората глава, после пак от първата и т.н., като всяка глава сменяше посоката на движението му.
    (Дъглас Адамс, Пътеводител на галактическия стопаджия, Бард, София, 2002)
    Напишете програма, която да определи дали Зейфод Бийблброкс ще се измъкне от тъпото тримерно пространство и ако да, колко са възможните различни пътища за достигане на нулата.

    На стандартния вход за всеки пример се задава точка от положителния октант на тримерното пространство - три цели положителни числа, не по-големи от 10.

    На стандартния изход за всеки пример се извежда по едно число - броят на възможните различни пътища до тримерната нула.