D. Cartons of milk

Olya 非常喜欢牛奶。如果她至少有 #cf_span[k] 盒牛奶，她每天会喝掉 #cf_span[k] 盒；否则她会喝掉所有剩下的牛奶。但有一个问题——保质期。每盒牛奶都有一个过期日期，过了这个日期就不能再喝了（但在写明的日期当天仍然可以喝）。因此，如果 Olya 的冰箱里有超过保质期的牛奶，她会将其扔掉。 Olya 不喜欢扔掉牛奶，因此在喝牛奶时，她会选择保质期最短的那一盒。这种策略显然能最小化被扔掉的牛奶数量，并在可能的情况下避免扔掉任何牛奶。 Olya 面临的主要问题是购买新牛奶。目前，Olya 的冰箱里有 #cf_span[n] 盒牛奶，每盒都有已知的保质期（以天为单位，表示距离过期还有多少天）。她去的商店里有 #cf_span[m] 盒牛奶，每盒的保质期也已知。 请找出 Olya 最多能买多少盒牛奶，使得她不需要扔掉任何一盒。假设 Olya 今天没有喝任何一盒牛奶。 第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k]（#cf_span[1 ≤ n, m ≤ 10^6], #cf_span[1 ≤ k ≤ n + m]）——分别表示 Olya 冰箱中的牛奶盒数、商店中的牛奶盒数以及 Olya 每天饮用的牛奶盒数。 第二行包含 #cf_span[n] 个整数 #cf_span[f1, f2, ..., fn]（#cf_span[0 ≤ fi ≤ 10^7]）——表示冰箱中每盒牛奶的保质期。保质期以“可延迟饮用的天数”表示。例如，保质期为 #cf_span[0] 表示必须今天喝掉，#cf_span[1] 表示最晚明天喝掉，以此类推。 第三行包含 #cf_span[m] 个整数 #cf_span[s1, s2, ..., sm]（#cf_span[0 ≤ si ≤ 10^7]）——表示商店中每盒牛奶的保质期，格式同上。 如果 Olya 无法喝完她冰箱里现有的所有牛奶，请输出 _-1_。 否则，第一行输出一个整数 #cf_span[x]，表示 Olya 最多能购买的牛奶盒数，使得她不需要扔掉任何一盒。第二行输出恰好 #cf_span[x] 个整数——表示应购买的牛奶的编号（按输入顺序编号，从 #cf_span[1] 开始）。编号不能重复，但可以任意顺序输出。如果有多个正确答案，输出任意一个即可。 在第一个例子中，#cf_span[k = 2]，Olya 有三盒牛奶，保质期分别为 #cf_span[0], #cf_span[1], #cf_span[1]（分别表示今天、明天、明天过期），商店中有 #cf_span[3] 盒保质期为 #cf_span[0] 的牛奶和 #cf_span[3] 盒保质期为 #cf_span[2] 的牛奶。Olya 可以购买三盒牛奶，例如一盒保质期为 #cf_span[0] 的和两盒保质期为 #cf_span[2] 的。 在第二个例子中，Olya 拥有的三盒牛奶全部今天过期，这意味着无论她是否购买额外的牛奶，都必须扔掉一些。 在第三个例子中，Olya 今天会喝掉 #cf_span[k = 2] 盒牛奶（一盒来自冰箱，一盒来自商店），剩下的那一盒明天喝。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k]（#cf_span[1 ≤ n, m ≤ 10^6], #cf_span[1 ≤ k ≤ n + m]）——分别表示 Olya 冰箱中的牛奶盒数、商店中的牛奶盒数以及 Olya 每天饮用的牛奶盒数。 第二行包含 #cf_span[n] 个整数 #cf_span[f1, f2, ..., fn]（#cf_span[0 ≤ fi ≤ 10^7]）——表示冰箱中每盒牛奶的保质期。保质期以“可延迟饮用的天数”表示。例如，保质期为 #cf_span[0] 表示必须今天喝掉，#cf_span[1] 表示最晚明天喝掉，以此类推。 第三行包含 #cf_span[m] 个整数 #cf_span[s1, s2, ..., sm]（#cf_span[0 ≤ si ≤ 10^7]）——表示商店中每盒牛奶的保质期，格式同上。 ## Output 如果 Olya 无法喝完她冰箱里现有的所有牛奶，请输出 _-1_。 否则，第一行输出一个整数 #cf_span[x]，表示 Olya 最多能购买的牛奶盒数，使得她不需要扔掉任何一盒。第二行输出恰好 #cf_span[x] 个整数——表示应购买的牛奶的编号（按输入顺序编号，从 #cf_span[1] 开始）。编号不能重复，但可以任意顺序输出。如果有多个正确答案，输出任意一个即可。 [samples] ## Note 在第一个例子中，#cf_span[k = 2]，Olya 有三盒牛奶，保质期分别为 #cf_span[0], #cf_span[1], #cf_span[1]（分别表示今天、明天、明天过期），商店中有 #cf_span[3] 盒保质期为 #cf_span[0] 的牛奶和 #cf_span[3] 盒保质期为 #cf_span[2] 的牛奶。Olya 可以购买三盒牛奶，例如一盒保质期为 #cf_span[0] 的和两盒保质期为 #cf_span[2] 的。 在第二个例子中，Olya 拥有的三盒牛奶全部今天过期，这意味着无论她是否购买额外的牛奶，都必须扔掉一些。 在第三个例子中，Olya 今天会喝掉 #cf_span[k = 2] 盒牛奶（一盒来自冰箱，一盒来自商店），剩下的那一盒明天喝。

**Definitions:** - Let $ n $: number of cartons currently in Olya’s fridge. - Let $ m $: number of cartons available in the shop. - Let $ k $: number of cartons Olya drinks per day. - Let $ F = \{f_1, f_2, \dots, f_n\} $: multiset of expiration dates (in days from today) of cartons in the fridge. - Let $ S = \{s_1, s_2, \dots, s_m\} $: multiset of expiration dates of cartons in the shop. **Constraints:** - Olya drinks exactly $ k $ cartons per day, **if at least $ k $ are available and not expired**. - If fewer than $ k $ cartons are available and not expired, she drinks **all** of them. - Cartons with expiration date $ d $ can be consumed on day $ d $ or earlier (i.e., on day $ t $, only cartons with $ d \geq t $ are valid). - Olya **always consumes the carton with the earliest expiration date** among available ones (greedy strategy). - Any carton with expiration date strictly less than the current day is discarded (thrown away). - Olya **does not drink any cartons today** before deciding what to buy. - Goal: **Maximize** the number $ x $ of cartons bought from the shop such that **no carton is ever thrown away** during the entire consumption process. **Objective:** Find the **maximum** $ x \in [0, m] $ such that, when adding any $ x $ cartons from $ S $ to $ F $, the greedy consumption process (earliest expiry first, daily consumption of $ \min(k, \text{available}) $) results in **zero discarded cartons**. If **even without buying any cartons**, Olya would be forced to discard at least one carton during consumption, output $ -1 $. --- **Formal Problem Statement:** Given multisets $ F $ and $ S $, and integer $ k $, determine the maximum $ x \leq m $ such that there exists a subset $ T \subseteq S $, $ |T| = x $, for which the following holds: Let $ U = F \cup T $, sorted in non-decreasing order: $ u_1 \leq u_2 \leq \dots \leq u_{n+x} $. Simulate consumption over days $ t = 0, 1, 2, \dots $: - On day $ t $, let $ A_t = \{ u_i \in U \mid u_i \geq t \} $ (available cartons on day $ t $). - Olya consumes $ \min(k, |A_t|) $ cartons from $ A_t $, **always choosing the ones with smallest expiration dates first**. - After consumption, remove the consumed cartons from $ U $. - If at any day $ t $, the number of cartons with expiration date $ < t $ is $ > 0 $, then **discard** occurs → invalid. We require that **no discard ever occurs** during the entire process. Equivalently, define the consumption schedule: Let $ U $ be sorted increasingly: $ u_1 \leq u_2 \leq \dots \leq u_{n+x} $. Then, for the consumption to be feasible without discard, it must hold that: > For all $ i \in \{1, 2, \dots, n+x\} $, the $ i $-th earliest-expiring carton must be consumed **on or before its expiration day**. Since $ k $ cartons are consumed per day, the $ i $-th carton (in sorted order) is consumed on day $ \left\lceil \frac{i}{k} \right\rceil - 1 $ (since day 0 consumes cartons 1 to $ k $, day 1 consumes $ k+1 $ to $ 2k $, etc.). Thus, the necessary and sufficient condition for feasibility is: $$ \forall i \in \{1, 2, \dots, n+x\}: \quad u_i \geq \left\lceil \frac{i}{k} \right\rceil - 1 $$ Let $ d_i = \left\lceil \frac{i}{k} \right\rceil - 1 $, the day on which the $ i $-th carton is consumed. Then, **the set $ U = F \cup T $ must satisfy** $ u_i \geq d_i $ for all $ i $. --- **Algorithmic Reformulation:** 1. **Check feasibility without buying any cartons:** - Sort $ F $: $ f_{(1)} \leq f_{(2)} \leq \dots \leq f_{(n)} $ - For $ i = 1 $ to $ n $: if $ f_{(i)} < \left\lceil \frac{i}{k} \right\rceil - 1 $, then output $ -1 $. 2. **Maximize $ x $:** - Sort $ S $: $ s_{(1)} \leq s_{(2)} \leq \dots \leq s_{(m)} $ - We want to choose a subset $ T \subseteq S $ of size $ x $, such that when combined with $ F $, the entire multiset $ U = F \cup T $, sorted increasingly, satisfies: $$ u_i \geq \left\lceil \frac{i}{k} \right\rceil - 1 \quad \forall i = 1, 2, \dots, n+x $$ - This is equivalent to: **greedily insert** the best (i.e., smallest expiration) cartons from $ S $ into the sorted sequence $ F $, and check the constraint at each position. - Strategy: - Merge $ F $ and $ S $ into one multiset, and sort all $ n+m $ cartons. - Use binary search on $ x \in [0, m] $: for a candidate $ x $, try to choose the $ x $ **best** cartons from $ S $ (i.e., smallest expiration dates) to add to $ F $, then check if the combined sorted sequence satisfies $ u_i \geq \left\lceil \frac{i}{k} \right\rceil - 1 $ for all $ i \in [1, n+x] $. - To check a candidate $ x $: - Take the $ x $ smallest cartons from $ S $, combine with $ F $, sort the result. - For each $ i \in [1, n+x] $, verify $ u_i \geq \left\lceil \frac{i}{k} \right\rceil - 1 $. - If all satisfy → candidate $ x $ is feasible. - Binary search over $ x $ from 0 to $ m $, find maximum feasible $ x $. 3. **Output the indices:** - Once maximum $ x $ is found, select the $ x $ cartons from $ S $ with the smallest expiration dates (breaking ties arbitrarily, since any valid set is acceptable). - Output their original input indices (1-indexed). --- **Final Mathematical Formulation:** Let $ F = \{f_1, \dots, f_n\} $, $ S = \{s_1, \dots, s_m\} $, $ k \in \mathbb{N} $. Define $ d_i = \left\lceil \frac{i}{k} \right\rceil - 1 $ for $ i \in \mathbb{N} $. Let $ U = F \cup T $, where $ T \subseteq S $, $ |T| = x $. Sort $ U $ increasingly: $ u_1 \leq u_2 \leq \dots \leq u_{n+x} $. Then, the maximum $ x $ such that: $$ \boxed{ \forall i \in \{1, 2, \dots, n+x\}: \quad u_i \geq \left\lceil \frac{i}{k} \right\rceil - 1 } $$ is the solution. If even for $ x = 0 $, the condition fails for some $ i \in \{1, \dots, n\} $, output $ -1 $. Otherwise, output the maximum such $ x $, and any $ x $ indices from $ S $ corresponding to the $ x $ smallest elements in $ S $ that make the condition hold.