1876A.md (2787B)
1 Source: https://codeforces.com/problemset/problem/1876/A 2 3 A. Helmets in Night Light 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Pak Chanek is the chief of a village named Khuntien. On one night filled with lights, Pak Chanek has a sudden and important announcement that needs to be notified to all of the $n$ residents in Khuntien. 22 23 First, Pak Chanek shares the announcement directly to one or more residents with a cost of $p$ for each person. After that, the residents can share the announcement to other residents using a magical helmet-shaped device. However, there is a cost for using the helmet-shaped device. For each $i$, if the $i$-th resident has got the announcement at least once (either directly from Pak Chanek or from another resident), he/she can share the announcement to at most $a_i$ other residents with a cost of $b_i$ for each share. 24 25 If Pak Chanek can also control how the residents share the announcement to other residents, what is the minimum cost for Pak Chanek to notify all $n$ residents of Khuntien about the announcement? 26 27 Input 28 29 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The following lines contain the description of each test case. 30 31 The first line contains two integers $n$ and $p$ ($1 \leq n \leq 10^5$; $1 \leq p \leq 10^5$) — the number of residents and the cost for Pak Chanek to share the announcement directly to one resident. 32 33 The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq10^5$) — the maximum number of residents that each resident can share the announcement to. 34 35 The third line contains $n$ integers $b_1,b_2,b_3,\ldots,b_n$ ($1\leq b_i\leq10^5$) — the cost for each resident to share the announcement to one other resident. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 38 39 Output 40 41 For each test case, output a line containing an integer representing the minimum cost to notify all $n$ residents of Khuntien about the announcement. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 6 3 51 52 2 3 2 1 1 3 53 54 4 3 2 6 3 6 55 56 1 100000 57 58 100000 59 60 1 61 62 4 94 63 64 1 4 2 3 65 66 103 96 86 57 67 ``` 68 69 Output 70 71 ``` 72 16 73 100000 74 265 75 ``` 76 77 Note 78 79 In the first test case, the following is a possible optimal strategy: 80 81 1. Pak Chanek shares the announcement directly to the $3$-rd, $5$-th, and $6$-th resident. This requires a cost of $p+p+p=3+3+3=9$. 82 2. The $3$-rd resident shares the announcement to the $1$-st and $2$-nd resident. This requires a cost of $b_3+b_3=2+2=4$. 83 3. The $2$-nd resident shares the announcement to the $4$-th resident. This requires a cost of $b_2=3$. 84 85 The total cost is $9+4+3=16$. It can be shown that there is no other strategy with a smaller cost.