Determine how many football kits are needed so that every player can be assigned a shirt and shorts of the right colors.
You are given the number of players and, for each player, the colors of the shirt and shorts they need. A kit consists of one shirt and one pair of shorts.
A shirt or pair of shorts can be used by at most one player. Players can only be assigned items of the exact required color.
Your task is to determine the minimum number of kits that must be prepared so that every player can receive both items they need.
In other words, for every color, if shirt[color] players need a shirt of that color and shorts[color] players need shorts of that color, then the number of kits needed for that color is the maximum of those two counts. Sum this over all colors.
n — the number of players.n lines contain two integers s_i and t_i, the colors of the shirt and shorts needed by the i-th player.Print a single integer — the minimum number of football kits required.
1 <= n <= 1000Example 1
Input
4 1 2 1 3 2 2 3 2
Output
4
Explanation
Color 1 needs 2 shirts and 1 pair of shorts, so 2 kits. Color 2 needs 1 shirt and 3 pairs of shorts, so 3 kits. Color 3 needs 1 shirt and 1 pair of shorts, so 1 kit. But each player contributes one shirt-color and one shorts-color need; the total minimum kits is the sum over colors after matching counts, which here is 4.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.