1211C.md (2031B)
1 Source: https://codeforces.com/problemset/problem/1211/C 2 3 C. Ice Cream 4 5 time limit per test 6 7 3 seconds 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 Summer in Berland lasts $n$ days, the price of one portion of ice cream on the $i$-th day is $c_i$. Over the summer, Tanya wants to eat exactly $k$ portions of ice cream. At the same time, on the $i$-th day, she decided that she would eat at least $a_i$ portions, but not more than $b_i$ ($a_i \le b_i$) portions. In other words, let $d_i$ be equal to the number of portions that she eats on the $i$-th day. Then $d_1+d_2+\dots+d_n=k$ and $a_i \le d_i \le b_i$ for each $i$. 22 23 Given that portions of ice cream can only be eaten on the day of purchase, find the minimum amount of money that Tanya can spend on ice cream in the summer. 24 25 Input 26 27 The first line contains two integers $n$ and $k$ ($1 \le n \le 2\cdot10^5$, $0 \le k \le 10^9$) — the number of days and the total number of servings of ice cream that Tanya will eat in the summer. 28 29 The following $n$ lines contain descriptions of the days, one description per line. Each description consists of three integers $a_i, b_i, c_i$ ($0 \le a_i \le b_i \le 10^9$, $1 \le c_i \le 10^6$). 30 31 Output 32 33 Print the minimum amount of money that Tanya can spend on ice cream in the summer. If there is no way for Tanya to buy and satisfy all the requirements, then print -1. 34 35 Examples 36 37 Input 38 39 ``` 40 3 7 41 3 5 6 42 0 3 4 43 3 3 3 44 ``` 45 46 Output 47 48 ``` 49 31 50 ``` 51 52 Input 53 54 ``` 55 1 45000 56 40000 50000 100000 57 ``` 58 59 Output 60 61 ``` 62 4500000000 63 ``` 64 65 Input 66 67 ``` 68 3 100 69 2 10 50 70 50 60 16 71 20 21 25 72 ``` 73 74 Output 75 76 ``` 77 -1 78 ``` 79 80 Input 81 82 ``` 83 4 12 84 2 5 1 85 1 2 2 86 2 3 7 87 3 10 4 88 ``` 89 90 Output 91 92 ``` 93 35 94 ``` 95 96 Note 97 98 In the first example, Tanya needs to eat $3$ portions of ice cream on the first day, $1$ portions of ice cream on the second day and $3$ portions of ice cream on the third day. In this case, the amount of money spent is $3\cdot6+1\cdot4+3\cdot3=31$. It can be shown that any other valid way to eat exactly $7$ portions of ice cream costs more.