Team Olympiad
Time limit2sMemory limit256 MB
Given n interactive and m ordinary problems with times p and q and a limit t, find the smallest team size (including Vasya, who can do both) so all problems get solved in time.
- Level
Medium4 of 10
- Topics
- Math, Greedy, Brute force, Implementation
- Solved
- No attempts yet
Problem
Vasya and his friends decided to take part in a new team olympiad. Unlike the olympiads he is used to, in this one a team may have any number of members. To win, a team must solve all the problems presented.
The olympiad offers problems of two types: n interactive problems and m ordinary problems. Each of Vasya's friends can solve only problems of one type. If a friend can solve interactive problems, then each problem takes him p minutes, and if ordinary problems, then q minutes. Vasya can solve both types, and like his friends he spends p minutes on an interactive problem and q minutes on an ordinary one.
The team members may use any number of computers to solve the problems. During the olympiad each problem is solved by exactly one member, and the members do not communicate with each other.
Help Vasya form a team that can win the olympiad of duration t minutes and has as few members as possible.
For example, if an olympiad of 100 minutes offers 10 interactive and 10 ordinary problems, and p = q = 30, then a team of 7 can be formed: Vasya, three friends who solve interactive problems, and three friends who solve ordinary problems. Each friend will solve three problems of his type, and Vasya will solve one interactive and one ordinary problem.
Input
The first line contains the number of test cases T (1 ≤ T ≤ 1000). The next T lines contain the test cases: five positive integers n, m, p, q, t, each not exceeding 10000. Also, p ≤ t and q ≤ t.
Output
For each test case, output a single number on a line: the minimum number of team members needed to win.