Problem F
Dream Team
Jiro Horikoshi is a young aircraft designer who is looking to create a team of aircraft engineers to help him design his first airplane. He wants to build a dream team of $12$ engineers. There are $N$ engineers that he can choose from, where the $i$-th engineer has a skill rating $a_i$ and a salary $s_i$. In order to promote a harmonious team enviornment, Jiro wants all the team members to be relatively equally skilled and equally paid. That is, the skill gap cannot exceed $P$ and the pay gap cannot exceed $Q$. As Jiro cannot spend too much (this being his first aircraft), can you help Jiro build the cheapest engineering team that would satisfy the requirement?
Input
The first line of the input contains three space-separated
integers $N \: (1 \leq N \leq
100), P \: (1 \leq P \leq 100)$, and $Q \: (1 \leq Q \leq 10^8)$,
representing the number of engineers to choose from, the
maximum skill gap, and the maximum pay gap, respectively.
The next line will contain $N$ integers $a_1, a_2, \dots a_N \: (1 \leq a_i \leq
100)$, with each $a_i$ representing the skill rating
for engineer $i$.
The last line will contain $N$ integers $s_1, s_2, \dots s_N \: (1 \leq s_i \leq
10^8)$, with each $s_i$ representing the salary for
engineer $i$.
Output
If there exists a team that satisfy the requirement, output “YES” on the first line and the cost of the cheapest team on the second line. Otherwise, only output “NO” on a single line.
Sample Input 1 | Sample Output 1 |
---|---|
5 5 100 1 2 3 4 5 100 88 49 10000 666 |
NO |
Sample Input 2 | Sample Output 2 |
---|---|
12 11 100 2 4 3 1 8 7 12 5 6 11 10 9 40 50 30 10 80 70 20 10 10 10 10 10 |
YES 350 |