Единственное отличие между легкой и сложной версиями — ограничечния.
Иван играет в компьютерную игру, содержащую микротранзакции для улучшения внешнего вида персонажей. Так как Иван хочет, чтобы его персонаж выглядел очень круто, он хочет использовать некоторые из этих микротранзакций — и он не хочет начинать играть до того момента, пока не получит их все.
Каждый день (с утра) Иван зарабатывает ровно один бурль.
Всего в игре есть \(n\) типов микротранзакций. Каждая микротранзакция обычно стоит \(2\) бурля и \(1\) бурль, если она на распродаже. Иван хочет использовать ровно \(k_i\) микротранзакций \(i\)-го типа (он покупает микротранзакции вечером).
Иван может использовать любое (возможно, нулевое) количество микротранзакций любых типов в течение любого дня (конечно, если ему хватает денег, чтобы это сделать). Если микротранзакция, которую он хочет использовать, находится на распродаже, то он может использовать ее за \(1\) бурль, иначе он может использовать ее за \(2\) бурля.
Также в игровом магазине есть \(m\) специальных предложений. \(j\)-е предложение \((d_j, t_j)\) означает, что микротранзакции \(t_j\)-го типа находятся на распродаже в течение \(d_j\)-го дня.
Иван хочет использовать все микротранзакции как можно раньше. Ваша задача — найти минимальный номер дня, когда он сможет использовать все микротранзакции, которые он хочет, и действительно сможет начать играть.
Выходные данные
Выведите одно целое число — минимальный номер дня, когда Иван сможет использовать все микротранзакции, которые он хочет, и действительно сможет начать играть.