AT_abc447_g [ABC447G] Div. 1 & Div. 2

Snuke is choosing problems to use in programming contests he is hosting. Snuke has $ N $ problem candidates numbered $ 1 $ to $ N $ , where problem candidate $ i $ has **difficulty** $ i $ , **genre** $ K_i $ , and **interest** $ A_i $ . Hoping to entertain participants of a wider range of skill levels, he plans to simultaneously hold two contests called **Div. 1** and **Div. 2**, each featuring four problems chosen from the $ N $ problem candidates with **pairwise distinct genres**. However, to conserve problem candidates, the two easier problems in Div. 1 and the two harder problems in Div. 2 will be the same, so only six problems in total will be used. More formally, the following holds: - Snuke chooses six problem candidates from the $ N $ candidates. Let the numbers of the chosen problem candidates in ascending order be $ i_1, i_2, \dots, i_6 $ . - Problem candidates $ i_1, i_2, i_3, i_4 $ are used in Div. 2, and they must be of pairwise distinct genres. That is, $ K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4} $ must be pairwise distinct. - Problem candidates $ i_3, i_4, i_5, i_6 $ are used in Div. 1, and they must be of pairwise distinct genres. That is, $ K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6} $ must be pairwise distinct. Determine whether there exists a valid choice of six problems satisfying the conditions, and if so, find the maximum total interest of the six chosen problems.

The input is given from Standard Input in the following format: > $ N $ $ K_1 $ $ A_1 $ $ K_2 $ $ A_2 $ $ \vdots $ $ K_N $ $ A_N $

If there exists a valid choice of six problems satisfying the conditions, output the maximum total interest of the six chosen problems; otherwise, output `-1`.

### Sample Explanation 1 For example, consider choosing problem candidates $ 1, 2, 3, 5, 6, 8 $ . In this case, $ K_{i_1}=1, K_{i_2}=3, K_{i_3}=2, K_{i_4}=4 $ are pairwise distinct, and $ K_{i_3}=2, K_{i_4}=4, K_{i_5}=3, K_{i_6}=5 $ are also pairwise distinct, so this is a valid choice. The total interest in this case is $ 9+4+3+6+3+7=32 $ , which is the maximum. ### Sample Explanation 2 There is no valid choice of six problems satisfying the conditions. ### Constraints - $ 6 \leq N \leq 10^5 $ - $ 1 \leq K_i \leq N $ - $ 1 \leq A_i \leq 10^9 $ - All input values are integers.