codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1470A.md (2497B)


      1 Source: https://codeforces.com/problemset/problem/1470/A
      2 
      3 A. Strange Birthday Party
      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 Petya organized a strange birthday party. He invited $n$ friends and assigned an integer $k_i$ to the $i$-th of them. Now Petya would like to give a present to each of them. In the nearby shop there are $m$ unique presents available, the $j$-th present costs $c_j$ dollars ($1 \le c_1 \le c_2 \le \ldots \le c_m$). It's not allowed to buy a single present more than once.
     22 
     23 For the $i$-th friend Petya can either buy them a present $j \le k_i$, which costs $c_j$ dollars, or just give them $c_{k_i}$ dollars directly.
     24 
     25 Help Petya determine the minimum total cost of hosting his party.
     26 
     27 Input
     28 
     29 The first input line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases.
     30 
     31 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 3 \cdot 10^5$) — the number of friends, and the number of unique presents available.
     32 
     33 The following line contains $n$ integers $k_1, k_2, \ldots, k_n$ ($1 \leq k_i \leq m$), assigned by Petya to his friends.
     34 
     35 The next line contains $m$ integers $c_1, c_2, \ldots, c_m$ ($1 \le c_1 \le c_2 \le \ldots \le c_m \le 10^9$) — the prices of the presents.
     36 
     37 It is guaranteed that sum of values $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of values $m$ over all test cases does not exceed $3 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case output a single integer — the minimum cost of the party.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 2
     49 5 4
     50 2 3 4 3 2
     51 3 5 12 20
     52 5 5
     53 5 4 3 2 1
     54 10 40 90 160 250
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 30
     61 190
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 1
     68 1 1
     69 1
     70 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 ```
     78 
     79 Note
     80 
     81 In the first example, there are two test cases. In the first one, Petya has $5$ friends and $4$ available presents. Petya can spend only $30$ dollars if he gives
     82 
     83 * $5$ dollars to the first friend.
     84 * A present that costs $12$ dollars to the second friend.
     85 * A present that costs $5$ dollars to the third friend.
     86 * A present that costs $3$ dollars to the fourth friend.
     87 * $5$ dollars to the fifth friend.
     88 
     89 In the second one, Petya has $5$ and $5$ available presents. Petya can spend only $190$ dollars if he gives
     90 
     91 * A present that costs $10$ dollars to the first friend.
     92 * A present that costs $40$ dollars to the second friend.
     93 * $90$ dollars to the third friend.
     94 * $40$ dollars to the fourth friend.
     95 * $10$ dollars to the fifth friend.