C. Петя и экзамен
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Экзамен состоит из $$$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$$$.

Помогите Пете определить максимальное количество баллов, которые он успеет набрать перед тем как уйдет с экзамена.

Входные данные

В первой строке находится число $$$m$$$ ($$$1 \le m \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания $$$m$$$ наборов входных данных, по три строки на каждый набор.

В первой строке каждого набора входных данных находятся четыре целых числа $$$n, T, a, b$$$ ($$$2 \le n \le 2\cdot10^5$$$, $$$1 \le T \le 10^9$$$, $$$1 \le a < b \le 10^9$$$) — количество задач, минут, отведенных на экзамен, время решения простой и сложной задачи, соответственно.

Во второй строке каждого набора входных данных находятся $$$n$$$ чисел $$$0$$$ или $$$1$$$, записанные через пробел: $$$i$$$-е число означает тип $$$i$$$-й задачи. Значение $$$0$$$ означает, что задача простая, а значение $$$1$$$ — сложная.

В третьей строке каждого набора входных данных находятся $$$n$$$ целых чисел $$$t_i$$$ ($$$0 \le t_i \le T$$$), где $$$i$$$-е число означает время, в которое $$$i$$$-я задача станет обязательной.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$

Выходные данные

Выведите ответы на $$$m$$$ заданных наборов входных данных. Для каждого набора выведите одно целое число — максимальное количество баллов, которые он успеет набрать перед тем как уйдет с экзамена.

Пример
Входные данные
10
3 5 1 3
0 0 1
2 1 4
2 5 2 3
1 0
3 2
1 20 2 4
0
16
6 20 2 5
1 1 0 1 0 0
0 8 2 9 11 6
4 16 3 6
1 0 1 1
8 3 5 6
6 20 3 6
0 1 0 0 1 0
20 11 3 20 16 17
7 17 1 6
1 1 0 1 0 0 0
1 7 0 11 10 15 10
6 17 2 6
0 0 1 0 0 1
7 6 3 7 10 12
5 17 2 5
1 1 1 1 0
17 11 10 6 4
1 1 1 2
0
1
Выходные данные
3
2
1
0
1
4
0
1
2
1