[PA 2024] Żelki

Luogu

IDLGP10357

Time3000ms

Memory1024MB

DifficultyP5

2024PA（波兰）

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Żelki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zel/)，感谢 Macaronlin 提供翻译** 共有 $n$ 种糖豆，有 $k$ 种颜色，第 $i$ 种糖豆颜色是 $k_i$，重量是 $m_i$，价格 $c_i$。现在要去购买糖豆，购买的糖豆需要包含所有 $k$ 种颜色，且每种颜色购买的数量相同。问对于在区间 $[0,m-1]$ 的每个整数 $r$，满足购买的糖豆总重量对 $m$ 取模为 $r$ 的购买方案中最小花费是多少？如果不存在满足条件的购买方案，则输出 $-1$。 ## Input 第一行三个整数 $n,k$ 和 $m\ (1\le n,k,m\le 7\,000)$，分别表示糖豆种类数，颜色数和参数。接下来 $n$ 行，每行三个整数 $k_i,m_i$ 和 $c_i\ (1\le k_i\le k,1\le m_i\le m,1\le c_i\le 10^9)$，分别表示第 $i$ 种糖豆的颜色，重量和价格。 ## Output 输出 $m$ 行，第 $i$ 行表示满足购买的所有糖豆总重量对 $m$ 取模为 $i-1$ 的情况中花费的最小值。如果不存在这样的情况，输出 $-1$。 [samples] ## Background PA 2024 3B ## Note 在第一组样例中： - 为了使糖豆的总重量能被 $m = 6$ 整除，可以不买任何糖豆，这样就不用花钱了。 - 为了使糖豆的总重量除以 $6$ 的余数为 $1$，应购买一颗第一种糖豆，两颗第二种糖豆，一颗第三种糖豆。这样花费为 $10$，得到两种颜色各两颗的糖豆，总重量等于 $7$。 - 为了使糖豆总重量除以 $6$ 的余数等于 $5$，应该买两颗第一种糖豆、三颗第二种糖豆和一颗第三种糖豆。第二个样例中没有第二种颜色的糖豆，所以唯一可行的方案是不买任何糖豆。

Samples

Input #1

Output #1

Input #2

2 3 3
1 1 1
3 1 1

Output #2

0
-1
-1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2024] Żelki",
    "description": {
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Żelki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zel/)，感谢 Macaronlin 提供翻译** 共有 $n$ 种糖豆，有 $k$ 种颜色，第 $i$ 种糖豆颜色是 $k_i$，重量是 $m_i$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10357"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Żelki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zel/)，感谢 Macaronlin 提供翻译**\n\n共有 $n$ 种糖豆，有 $k$ 种颜色，第 $i$ 种糖豆颜色是 $k_i$，重量是 $m_i$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments