Cooking Class
本题没有可用的提交语言。
Description
Autumn is training to pursue a career as a code chef! In order to learn how to prepare the tastiest bytes to eat, she is going to enter a cooking competition.
Also participating in the competition are $N$ other competitors of skill levels $S_1, S_2, \dots, S_N$ whereas Autumn has a current skill level of $S_A$.
Additionally, Autumn is going to prepare for the competition by attending exactly one of $M$ different cooking classes. The $i$th cooking class has an associated value $P_i$ such that if Autumn attends class $i$, her new cooking skill level will become $S_A + P_i$. The rest of the competitors are too cocky and choose not to attend any cooking classes before the competition.
It turns out that the cooking competition involves no luck and is entirely skill-based. As such, a competitor's rank in the competition is directly correlated with their rank. A higher-skilled contestant will always outrank a contestant with a lower skill level, and equally skilled competitors will always tie for the same rank. Knowing that Autumn will attend exactly one of the $M$ cooking classes, please help her figure out what the best rank she can achieve in the cooking competition is.
Note: The contestant with the highest skill level will be of rank 1. If there are ties, all contestants tied with each other will have the same rank and then the ranking will proceed by skipping the numbers between the tied rank and the sum of the rank and the number of tied contestants (for example, if there are three contestants tied with the highest skill level, they they will all be rank 1, and the next contestant will be rank 4, and so on).
The input will begin with a line containing two space-separated integers, $N\ (1 \leq N \leq 2 \cdot 10^5)$ and $M\ (1 \leq M \leq 2 \cdot 10^5)$ denoting the number of contestants other than Autumn and the number of potential cooking classes Autumn may choose from, respectively.
The next line will consist of $N + 1$ space-separated integers, $S_1, S_2, \dots, S_N$ and $S_A\ (1 \leq S_1, S_2, \dots, S_N, S_A \leq 10^9)$, denoting the skill levels of the other contestants as well as Autumn's initial skill level, respectively.
The final line will consist of $M$ space-separated integers, $P_1, P_2, \dots, P_M\ (1 \leq P_1, P_2, \dots, P_M \leq 10^9)$, denoting the skill boosts that Autumn will attain from attending each of the respective cooking classes.
The output should consist of exactly one positive integer denoting the best ranking that Autumn can achieve by maximizing her skill level through attending exactly one of the potential cooking classes and boosting her skill level by the respective amount.
Input
The input will begin with a line containing two space-separated integers, $N\ (1 \leq N \leq 2 \cdot 10^5)$ and $M\ (1 \leq M \leq 2 \cdot 10^5)$ denoting the number of contestants other than Autumn and the number of potential cooking classes Autumn may choose from, respectively.
The next line will consist of $N + 1$ space-separated integers, $S_1, S_2, \dots, S_N$ and $S_A\ (1 \leq S_1, S_2, \dots, S_N, S_A \leq 10^9)$, denoting the skill levels of the other contestants as well as Autumn's initial skill level, respectively.
The final line will consist of $M$ space-separated integers, $P_1, P_2, \dots, P_M\ (1 \leq P_1, P_2, \dots, P_M \leq 10^9)$, denoting the skill boosts that Autumn will attain from attending each of the respective cooking classes.
Output
The output should consist of exactly one positive integer denoting the best ranking that Autumn can achieve by maximizing her skill level through attending exactly one of the potential cooking classes and boosting her skill level by the respective amount.
5 5
3 3 3 4 5 2
1 2 3 4 5
1
Note
In the sample test case, it would be optimal for Autumn to attend cooking lesson 5 which has an associated skill boost value $P_5 = 5$ so that her total skill value becomes $S_A + P_5 = 2 + 5 = 7$. This way, she outranks all of the other competitors in terms of skills, earning her the rank 1 spot.