2154: Фабрика

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 35,00 (partial)
Time limit: 1.0s
Memory limit: 500M
Input: stdin
Output: stdout
Author:
zvit
Problem type

Фабрика переробляє руду протягом ~n~ стадій. Ціль отримати як можна більше матеріалу типу ~n~.

На кожній стадії доступно кілька машин. Машина переробляє матеріал типу ~T_i~ в матеріал типу ~T_{i+1}~. Кожна окрема машина характеризується тим, скільки матеріалу вона споживає і скільки виробляє: ~I_i~ та ~O_i~.

Оскільки фабрика має обмежений розмір складу ~k~, це значить, що матеріали зберігатимуться разом, тобто склад має вміщати весь матеріал типів ~i~ та ~i+1~, який було вироблено і який залишився.

Зайві матеріали можна викинути з складу. Якщо якась кількість матеріалу була викинута з складу, у фабрики більше не буде до неї доступу.

Етапи переробки мають виконуватись поступово, тобто спершу потрібно переробити тип ~1~ на тип ~2~, потім тип ~2~ на тип ~3~, і так далі, поки не виготовимо бажану кількість типу ~n~.

На початку процесу в наявності лише ~s~ одиниць матеріалу типу ~1~.

Для кожного етапу існує хоча б одна машина.

Визначіть максимальну можливу кількість матеріалу типу ~n~, яку можна отримати.

Обмеження

  • ~(2 \le n \le 30)~
  • ~(n-1 \le m \le 500)~
  • ~(1 \le s \le k \le 10^4)~
  • ~(1 \le T_i \le n-1)~
  • ~(1 \le I_i, O_i \le k)~

Input

~n~ ~m~

~s~ ~k~

~T_1~ ~I_1~ ~O_1~

~T_2~ ~I_2~ ~O_2~

~\vdots~ ~\vdots~ ~\vdots~

~T_m~ ~I_m~ ~O_m~

Output

Максимальна кількість матеріалу типу ~n~, яку можна отримати.

Sample Input 1

3 5
5 5
1 5 4
1 2 3
1 1 2
2 1 1
2 3 4

Sample Output 1

5

Sample Input 2

4 4
11 24
1 2 3
1 1 1
2 1 5
3 3 4

Sample Output 2

24

Sample Input 3

2 1
4 7
1 2 4

Sample Output 3

7

Sample Input 4

2 1
7 7
1 3 5

Sample Output 4

5

Коментарі

Please read the guidelines before commenting.


  • 0
    Новачук  commented on Лис. 9, 2025, 4:28 після полудня

    А що зберігає змінна m?


    • 0
      zvit  commented on Лис. 10, 2025, 6:21 до полудня

      зверніть увагу на приклад вхідних


  • 0
    zhukso  commented on Лис. 8, 2025, 10:55 до полудня
    • Чи може одна машина на етапі виконувати роботу декілька разів?
    • Чи можуть декілька різних машин на етапі виконувати роботу одночасно?
    • Чи вірно, що машина не може обробляти частину матеріалу і не може бути запущена, якщо на складі немає місця для її продукціі після споживаня сировини?
    • Кожна машина існує в одному екземплярі (що не виключає появи однакових машин)?

    • 0
      judge  commented on Лис. 8, 2025, 11:07 до полудня
      1. Так
      2. Це не впливає на задачу
      3. Так
      4. Це не впливає на задачу через пункт (1)

  • 0
    Folela  commented on Лис. 6, 2025, 12:21 після полудня

    Машини задаються сортованими по T?


    • 0
      zvit  commented on Лис. 6, 2025, 12:37 після полудня

      ні


  • 0
    zoi095  commented on Лис. 5, 2025, 8:27 після полудня

    чому в четвертому тесті ми не можем спершу викинути один матеріал (отже на складі 6 матеріалів першого типу і 1 вільне місце). Потім переробити 3 матеріала першого типу на 5 матеріалів другого типу(після використання 3 матеріалів першого типу в нас на складі стає 4 вільні місця, які ми можемо заповнити виготовленими матеріалами другого типу. Отже на складі вже 4 матеріали другого типу і 3 матеріали першого). Потім останні 3 матеріали першого типу переробляєм на 5 матеріалів другого типу (3 нові звільнені місця одразу заповнюємо нововиготовленими матеріалами другого типу). В кінці кінців отримуємо повний склад елементів другого типу (7 штук)


    • 0
      judge  commented on Лис. 6, 2025, 9:37 до полудня

      Що ви пропонуєте покроково:

      Тип 1 | Тип 2

      1. 7 | 0
      2. 6 | 0
      3. 6-3 | 0+5 Але 6-3+5 = 8, що більше ніж можна вмістити на склад, тобто щоб переробити матеріали потрібно щоб було місце для нововиготовленних матеріалів, їх можна викидати тільки зі складу, тобто спершу всі матеріали мають опинитись на складі!

  • 0
    pcheloveks69  commented on Лис. 3, 2025, 11:59 до полудня

    Під послідовністю виконання операцій мається на увазі, що операція j -> j + 1, не може бути виконана після i -> i + 1, якщо i > j?


    • 1
      judge  commented on Лис. 3, 2025, 2:26 після полудня

      Навпаки (напевно ви це і мали на увазі):

      Якщо i<j, то спершу i -> i+1, а потім j -> j+1


  • 0
    pcheloveks69  commented on Лис. 3, 2025, 11:16 до полудня

    Чи займає матеріал типу n місце на складі?


    • 1
      judge  commented on Лис. 3, 2025, 2:27 після полудня

      Так