2154: Фабрика
Переглянути як PDFФабрика переробляє руду протягом ~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
Коментарі
А що зберігає змінна m?
зверніть увагу на приклад вхідних
Машини задаються сортованими по T?
ні
чому в четвертому тесті ми не можем спершу викинути один матеріал (отже на складі 6 матеріалів першого типу і 1 вільне місце). Потім переробити 3 матеріала першого типу на 5 матеріалів другого типу(після використання 3 матеріалів першого типу в нас на складі стає 4 вільні місця, які ми можемо заповнити виготовленими матеріалами другого типу. Отже на складі вже 4 матеріали другого типу і 3 матеріали першого). Потім останні 3 матеріали першого типу переробляєм на 5 матеріалів другого типу (3 нові звільнені місця одразу заповнюємо нововиготовленими матеріалами другого типу). В кінці кінців отримуємо повний склад елементів другого типу (7 штук)
Що ви пропонуєте покроково:
Тип 1 | Тип 2
Під послідовністю виконання операцій мається на увазі, що операція j -> j + 1, не може бути виконана після i -> i + 1, якщо i > j?
Навпаки (напевно ви це і мали на увазі):
Якщо i<j, то спершу i -> i+1, а потім j -> j+1
Чи займає матеріал типу n місце на складі?
Так