1310A.md (1859B)
1 Source: https://codeforces.com/problemset/problem/1310/A 2 3 A. Recommendations 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 VK news recommendation system daily selects interesting publications of one of $n$ disjoint categories for each user. Each publication belongs to exactly one category. For each category $i$ batch algorithm selects $a_i$ publications. 22 23 The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of $i$-th category within $t_i$ seconds. 24 25 What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm. 26 27 Input 28 29 The first line of input consists of single integer $n$ — the number of news categories ($1 \le n \le 200\,000$). 30 31 The second line of input consists of $n$ integers $a_i$ — the number of publications of $i$-th category selected by the batch algorithm ($1 \le a_i \le 10^9$). 32 33 The third line of input consists of $n$ integers $t_i$ — time it takes for targeted algorithm to find one new publication of category $i$ ($1 \le t_i \le 10^5)$. 34 35 Output 36 37 Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size. 38 39 Examples 40 41 Input 42 43 ``` 44 5 45 3 7 9 7 8 46 5 2 5 7 5 47 ``` 48 49 Output 50 51 ``` 52 6 53 ``` 54 55 Input 56 57 ``` 58 5 59 1 2 3 4 5 60 1 1 1 1 1 61 ``` 62 63 Output 64 65 ``` 66 0 67 ``` 68 69 Note 70 71 In the first example, it is possible to find three publications of the second type, which will take 6 seconds. 72 73 In the second example, all news categories contain a different number of publications.