Вы играете в компьютерную игру. В этой игре вы являетесь главой партии из \(m\) героев, и вам нужно зачистить подземелье, в котором находится \(n\) монстров. Каждый монстр характеризуется своей силой \(a_i\). Каждый герой характеризуется своей силой \(p_i\) и выносливостью \(s_i\).
Герои чистят подземелье день за днем. В начале каждого дня вы выбираете героя (ровно одного), который пойдет в подземелье в этот день.
Когда герой заходит в подземелье, он начинает сражаться с первым монстром, не побежденным в прошлые дни (т. е. если уже было побеждено \(k\) монстров, то этот герой будет сражаться с монстром под номером \(k + 1\)). Когда герой сражается с монстром, возможно два варианта:
- если сила монстра строго больше силы героя, то герой уходит из подземелья и день заканчивается;
- иначе монстр считается побежденным.
После победы над монстром герой либо продолжает сражаться с монстрами, либо уходит из подземелья. Он уходит, если он в этот день победил количество монстров, равное его выносливости (таким образом, \(i\)-й герой не может победить больше \(s_i\) монстров в течение одного дня), либо если все монстры побеждены — в противном случае герой сражается со следующим монстром. Когда герой покидает пещеру, текущий день заканчивается.
Ваша задача — победить всех монстров. Какое минимальное количество дней вам понадобится для этого? Каждый день вы выбираете ровно одного героя; возможно, некоторые герои не будут сражаться вообще, а некоторые будут сражаться несколько раз.
Выходные данные
На каждый набор входных данных выведите одно число — минимальное количество дней, которое вам нужно потратить для победы над всеми монстрами (или \(-1\), если это невозможно).