Задача . D. Друзья и ресторан

Компания из \(n\) друзей решила сходить в ресторан. Каждый из друзей планирует сделать заказ на \(x_i\) бурлей, а всего у него есть \(y_i\) бурлей (\(1 \le i \le n\)).

Компания решила разбить посещение ресторана на несколько дней. Каждый день в ресторан отправляется некоторая группа из хотя бы двух друзей. Каждый из друзей посещает ресторан не более одного раза (то есть эти группы не пересекаются). Эти группы должны удовлетворять условию: суммарный бюджет каждой группы должен быть не меньше суммы, которую собираются потратить друзья из группы в ресторане. Другими словами, сумма всех значений \(x_i\) в группе не должна превышать сумму значений \(y_i\) в группе.

Какое максимальное количество дней друзья могут посещать ресторан?

Например, пусть есть \(n = 6\) друзей, для которых \(x\) = [\(8, 3, 9, 2, 4, 5\)], а \(y\) = [\(5, 3, 1, 4, 5, 10\)]. Тогда:

• Первый и шестой друзья могут пойти в ресторан в первый день. Они потратят в ресторане \(8+5=13\) бурлей, а их суммарный бюджет составляет \(5+10=15\) бурлей. Так как \(15 \ge 13\), то они в самом деле могут образовать группу.
• Друзья с номерами \(2, 4, 5\) могут образовать вторую группу. Они потратят в ресторане \(3+2+4=9\) бурлей, а их общий бюджет составит \(3+4+5=12\) бурлей (\(12 \ge 9\)).

Можно показать, что образовать большее число групп так, чтобы в каждой группе было хотя бы два друга и можно было оплатить счёт, они не смогут.

Таким образом, максимальное количество групп, на которое могут разбиться друзья равно \(2\). Друзья будут посещать ресторан максимум два дня. Отметим, что \(3\)-й из друзей не посетит ресторан вообще.

Выведите максимальное количество дней посещения ресторана по заданным \(n\), \(x\) и \(y\).