Петя пришел на экзамен по математике и хочет решить как можно больше задач. Он подготовился и внимательно изучил правила, по которым проходит экзамен.
Экзамен состоит из \(n\) задач, которые можно решать в течении \(T\) минут. Таким образом, экзамен начинается в момент времени \(0\), а заканчивается — в момент времени \(T\). Петя может уйти с экзамена в любой целочисленный момент времени от \(0\) до \(T\), включительно.
Все задачи делятся на два типа:
- простые задачи — на решение каждой простой задачи у Пети уходит ровно \(a\) минут;
- сложные задачи — на решение каждой сложной задачи у Пети уходит ровно \(b\) минут (\(b > a\)).
Таким образом, если в момент времени \(x\) Петя приступает к решению простой задачи, то она будет решена в момент времени \(x+a\). Аналогично, если в момент времени \(x\) Петя приступает к решению сложной задачи, то она будет решена в момент времени \(x+b\).
Про каждую задачу Пете известно сложная она или простая. Помимо этого, для каждой задачи определен момент времени \(t_i\) (\(0 \le t_i \le T\)), в который она станет обязательной. Если Петя уходит с экзамена в момент времени \(s\) и есть такая задача \(i\), что \(t_i \le s\) и он её не решил, то считается, что за весь экзамен он получит \(0\) баллов. В противном случае (то есть, если он решил все такие задачи, для которых \(t_i \le s\)) он получит количество баллов, равное количеству решенных задач. Отметим, что уходя в момент времени \(s\) Петя может иметь решенными как «обязательные», так и «необязательные» задачи.
Например, если \(n=2\), \(T=5\), \(a=2\), \(b=3\), первая задача является сложной и для неё \(t_1=3\) и вторая задача является простой и для неё \(t_2=2\), то:
- если он уходит в момент времени \(s=0\), то он получит \(0\) баллов, так как не успеет решить ни одной задачи;
- если он уходит в момент времени \(s=1\), то он получит \(0\) баллов, так как не успеет решить ни одной задачи;
- если он уходит в момент времени \(s=2\), то он может получить \(1\) балл, решив задачу с номером \(2\) (решать её надо в промежуток от \(0\) до \(2\));
- если он уходит в момент времени \(s=3\), то он получит \(0\) баллов, так как к этому моменту времени обе задачи станут обязательными к решению, но решить их обе он не успеет;
- если он уходит в момент времени \(s=4\), то он получит \(0\) баллов, так как к этому моменту времени обе задачи станут обязательными к решению, но решить их обе он не успеет;
- если он уходит в момент времени \(s=5\), то он может получить \(2\) балла, решив все задачи.
Таким образом, ответ на этот тест равен \(2\).
Помогите Пете определить максимальное количество баллов, которые он успеет набрать перед тем как уйдет с экзамена.