C. Songs Compression

Codeforces

IDCF1015C

Time1000ms

Memory256MB

Difficulty—

sortings

English · Original

Chinese · Translation

Formal · Original

Ivan has $n$ songs on his phone. The size of the $i$\-th song is $a_i$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty. Ivan wants to copy all $n$ songs to the flash drive. He can compress the songs. If he compresses the $i$\-th song, the size of the $i$\-th song reduces from $a_i$ to $b_i$ bytes ($b_i < a_i$). Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most $m$. He can compress _any_ subset of the songs (not necessarily contiguous). Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to $m$). If it is impossible to copy all the songs (even if Ivan compresses all the songs), print "_\-1_". Otherwise print the minimum number of songs Ivan needs to compress. ## Input The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 1 \le m \le 10^9$) — the number of the songs on Ivan's phone and the capacity of Ivan's flash drive. The next $n$ lines contain two integers each: the $i$\-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$, $a_i > b_i$) — the initial size of the $i$\-th song and the size of the $i$\-th song after compression. ## Output If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print "_\-1_". Otherwise print the minimum number of the songs to compress. [samples] ## Note In the first example Ivan can compress the first and the third songs so after these moves the sum of sizes will be equal to $8 + 7 + 1 + 5 = 21 \le 21$. Also Ivan can compress the first and the second songs, then the sum of sizes will be equal $8 + 4 + 3 + 5 = 20 \le 21$. Note that compressing any single song is not sufficient to copy all the songs on the flash drive (for example, after compressing the second song the sum of sizes will be equal to $10 + 4 + 3 + 5 = 22 > 21$). In the second example even if Ivan compresses all the songs the sum of sizes will be equal $8 + 4 + 1 + 4 = 17 > 16$.

Ivan 有 $n$ 首歌在他的手机上。第 $i$ 首歌的大小为 $a_i$ 字节。Ivan 还有一个闪存盘，最多可以容纳 $m$ 字节。最初，他的闪存盘是空的。 Ivan 希望将所有 $n$ 首歌复制到闪存盘中。他可以压缩这些歌曲。如果他压缩第 $i$ 首歌，该歌的大小将从 $a_i$ 字节减少到 $b_i$ 字节（$b_i < a_i$）。 Ivan 可以压缩任意子集的歌曲（可能为空），并复制所有歌曲到闪存盘，只要它们的总大小不超过 $m$。他可以压缩任意子集的歌曲（不一定是连续的）。 Ivan 希望找到他需要压缩的最少歌曲数量，使得所有歌曲都能装入闪存盘（即它们的总大小小于或等于 $m$）。如果即使压缩所有歌曲也无法复制所有歌曲，请输出 "_-1_"。否则，输出 Ivan 需要压缩的最少歌曲数量。输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n lt.eq 10^5, 1 lt.eq m lt.eq 10^9$) —— Ivan 手机上的歌曲数量和闪存盘的容量。接下来的 $n$ 行每行包含两个整数：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 lt.eq a_i, b_i lt.eq 10^9$, $a_i > b_i$) —— 第 $i$ 首歌的初始大小和压缩后的大小。如果无法通过压缩部分歌曲使所有歌曲装入闪存盘，请输出 "_-1_"。否则输出需要压缩的最少歌曲数量。在第一个例子中，Ivan 可以压缩第一首和第三首歌，压缩后总大小为 $8 + 7 + 1 + 5 = 21 lt.eq 21$。Ivan 也可以压缩第一首和第二首歌，此时总大小为 $8 + 4 + 3 + 5 = 20 lt.eq 21$。注意，仅压缩任意一首歌不足以使所有歌曲装入闪存盘（例如，仅压缩第二首歌后总大小为 $10 + 4 + 3 + 5 = 22 > 21$）。在第二个例子中，即使压缩所有歌曲，总大小仍为 $8 + 4 + 1 + 4 = 17 > 16$。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n lt.eq 10^5, 1 lt.eq m lt.eq 10^9$) —— Ivan 手机上的歌曲数量和闪存盘的容量。接下来的 $n$ 行每行包含两个整数：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 lt.eq a_i, b_i lt.eq 10^9$, $a_i > b_i$) —— 第 $i$ 首歌的初始大小和压缩后的大小。 ## Output 如果无法通过压缩部分歌曲使所有歌曲装入闪存盘，请输出 "_-1_"。否则输出需要压缩的最少歌曲数量。 [samples] ## Note 在第一个例子中，Ivan 可以压缩第一首和第三首歌，压缩后总大小为 $8 + 7 + 1 + 5 = 21 lt.eq 21$。Ivan 也可以压缩第一首和第二首歌，此时总大小为 $8 + 4 + 3 + 5 = 20 lt.eq 21$。注意，仅压缩任意一首歌不足以使所有歌曲装入闪存盘（例如，仅压缩第二首歌后总大小为 $10 + 4 + 3 + 5 = 22 > 21$）。在第二个例子中，即使压缩所有歌曲，总大小仍为 $8 + 4 + 1 + 4 = 17 > 16$。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of songs. Let $ m \in \mathbb{Z}^+ $ be the flash drive capacity. For each song $ i \in \{1, \dots, n\} $, let: - $ a_i \in \mathbb{Z}^+ $ be the original size of song $ i $, - $ b_i \in \mathbb{Z}^+ $ be the compressed size of song $ i $, with $ b_i < a_i $. Let $ S = \sum_{i=1}^n a_i $ be the total size without compression. Let $ S_{\min} = \sum_{i=1}^n b_i $ be the total size with all songs compressed. Let $ d_i = a_i - b_i > 0 $ be the size reduction achieved by compressing song $ i $. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. $ 1 \le m \le 10^9 $ 3. $ 1 \le b_i < a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum number $ k \in \{0, 1, \dots, n\} $ such that there exists a subset $ C \subseteq \{1, \dots, n\} $ with $ |C| = k $ and $$ \sum_{i=1}^n a_i - \sum_{i \in C} d_i \le m $$ Equivalently: $$ \sum_{i \in C} d_i \ge S - m $$ If $ S_{\min} > m $, output $ -1 $. Otherwise, find the smallest $ k $ such that the sum of the $ k $ largest $ d_i $ values is at least $ S - m $.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Songs Compression",
    "description": {
      "content": "Ivan has $n$ songs on his phone. The size of the $i$\\-th song is $a_i$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty. Ivan wants to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1015C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan has $n$ songs on his phone. The size of the $i$\\-th song is $a_i$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty.\n\nIvan wants to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ivan 有 $n$ 首歌在他的手机上。第 $i$ 首歌的大小为 $a_i$ 字节。Ivan 还有一个闪存盘，最多可以容纳 $m$ 字节。最初，他的闪存盘是空的。\n\nIvan 希望将所有 $n$ 首歌复制到闪存盘中。他可以压缩这些歌曲。如果他压缩第 $i$ 首歌，该歌的大小将从 $a_i$ 字节减少到 $b_i$ 字节（$b_i < a_i$）。\n\nIvan 可以压缩任意子集的歌曲（可能为空），并...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of songs.  \nLet $ m \\in \\mathbb{Z}^+ $ be the flash drive capacity.  \nFor each song $ i \\in \\{1, \\dots, n\\} $, let:  \n- $ a_i \\in \\mathbb{Z}^...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments