22103번 - Командная олимпиада 다국어

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

На олимпиаде предлагаются задачи двух типов: n интерактивных и m обычных задач. Каждый из друзей Васи умеет решать только задачи одного типа. Если друг умеет решать интерактивные задачи, то у него на каждую задачу уходит p минут, а если обычные — то q минут. Вася же умеет решать и те, и другие задачи, как и его друзья, он тратит p минут на интерактивную задачу и q минут на обычную.

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

Помогите Васе составить команду, которая сможет победить в олимпиаде продолжительностью t минут таким образом, чтобы в ней было как можно меньше человек.

Например, если на олимпиаде продолжительностью 100 минут предлагается 10 интерактивных и 10 обычных задач, p = q = 30, то можно составить команду из 7 человек: Васи, трех друзей, которые решают интерактивные задачи, и трех друзей, которые решают обычные задачи. Каждый из друзей решит по три задачи своего типа, а Вася решит одну интерактивную и одну обычную задачу.

В первой строке задано число тестовых наборов T (1 ≤ T ≤ 1000). В следующих T строках заданы тестовые наборы: по пять целых положительных чисел n, m, p, q, t, каждое из которых не превышает 10000. Также, p ≤ t и q ≤ t.

Для каждого тестового набора выведите единственное число на строке — минимальное число участников команды, необходимое, чтобы победить.