// Author: Ivan Teo
// Created: Mon Nov 11 23:23:21 2024
#define TASKNAME "daydep"
/*
⣿⣧⢿⣏⢻⣿⣦⣿⣿⣿⣿⣏⣿⣿⣾⣿⣿⣿⣾⣿⣿⣻⣿⣿⢿⡿⣿⢹⠁⢹⣾⣷⣧⣿⢽⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣏⣶⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣧⣿⣿⣏
⣿⣿⡜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣯⣿⣿⣿⣿⢾⣿⣿⣾⡇⢸⣿⣿⣿⣿⢽⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿
⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠓⠈⣫⠝⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠁⠁⠃⠸⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⠃⠋⠁⣠⠞⠁⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠹⠻⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡝⢇⠔⢃⠜⠁⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠲⣴⠏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⢹⢔⣵⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡻⣷⣾⢻⣿⣿⣿⣿⣿⣿⣿⡿⣿
⣿⣿⣿⣿⣿⣿⡟⢧⣷⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⡻⡿⣾⢿⣿⣿⣿⣿⣿⣿⢣⣯
⢸⣿⣿⣿⣿⣿⣣⣫⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢱⣿⣿⣦⣻⣿⣿⣿⣿⣿⣴⣿
⣿⣿⣿⣿⣿⢙⠝⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣿⣿⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠃⢷⡿⣟⣽⣿⣿⣿⣷⣿⣿
⣾⣿⣿⡿⠉⢊⣾⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣜⠉⢻⣿⣿⣿⣿⡾
⣿⣿⣿⡇⠀⢠⣏⣽⠀⠀⠀⠀⠀⠀⢤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣇⠀⢸⣿⣿⣿⣿⢣
⣿⣿⣿⡇⠀⢈⣷⢹⠀⡇⠀⠀⠀⢀⣀⣹⣮⠉⠑⠴⠖⠢⠤⠤⠄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠤⠤⠤⠒⠒⢈⣉⣥⣖⣀⠀⠀⠀⠀⢀⠀⠀⣸⣇⠀⢸⣿⣿⣿⡟⠘
⣿⣿⣿⡇⢠⣿⣿⢠⢠⣇⠀⠀⠀⠀⠀⠈⢿⢿⡷⣦⣉⠱⢍⣀⡀⠸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⢀⣠⠤⢐⣾⠿⣿⠟⠉⠀⠀⠀⠀⢻⣞⣄⠀⢿⣿⡀⠘⣿⣿⣿⣿⣰
⣿⣿⣿⡇⢸⢸⣿⡼⢸⡿⠁⢀⣤⠤⠖⠒⠲⠾⣿⣦⡍⠓⣄⠈⠉⠉⢿⡄⠀⠀⠀⠀⠀⠀⠀⢀⣾⠋⠉⠁⠀⠖⠉⣡⣮⡷⠖⠒⠲⠦⠤⣠⠄⢻⣿⠀⢸⣿⣇⠀⣿⣿⣿⣿⡁
⣿⣿⣿⣇⣿⣼⡿⣱⣿⣧⠾⠛⠁⠀⠀⠲⠖⠒⠠⣌⡛⢦⡈⠀⡈⠂⠘⣿⠀⠀⠀⠀⠀⠀⢀⣾⠏⠐⠂⡀⣺⣶⢟⣫⠤⠐⠒⠂⠀⠀⠀⠉⠓⢦⣿⣦⣸⣿⣿⡇⣿⣿⣿⣿⣧
⣿⣿⣿⣿⣿⣟⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠈⠢⡛⣦⢳⣄⠀⠘⢧⠀⠀⠀⠀⠀⢰⠏⠀⢀⣜⣿⣿⡵⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣝⣿⡇⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡿⣼⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢱⠈⣗⢻⣤⣉⡉⣇⠀⠀⠀⢠⠏⣉⡥⡿⢿⢿⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⢿⣯⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⣀⣠⣤⣤⣤⣤⣤⣀⡀⠀⠀⠂⡌⡇⢳⡀⠉⢹⡉⠉⠉⡟⠉⠀⣼⠁⡇⠆⢀⠀⠀⣀⣤⣤⣤⣤⣤⣄⣀⡀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⡿⠋
⠘⢿⣿⡟⢻⣿⣷⣤⣤⣴⣾⣿⣿⣿⠿⠟⠛⠛⠿⠿⣿⣷⣦⣀⠘⠄⢿⡿⢤⠈⢃⡆⣒⠹⢁⣖⡇⠀⠂⢀⣬⣾⣿⡿⠿⠟⠛⠻⠿⣿⣿⣿⣿⣦⣤⣤⣽⣿⣿⢻⣿⣿⠟⣠⡴
⢳⣸⣿⠁⠮⣿⣿⣿⣿⣿⣿⡿⠋⠁⢀⣠⣤⣤⣄⡀⠈⠹⢿⣿⣷⡄⣸⣹⡏⠀⢸⣿⡇⠀⢸⣿⢣⢀⣴⣿⣿⠟⠉⠀⣀⣤⣤⣤⣀⠀⠙⢿⣿⣿⣿⣿⣿⣿⡯⡂⢿⣧⣼⣋⣤
⣝⣿⡟⢀⣹⣿⣿⣿⣿⣿⡿⠁⠀⡰⢿⣿⣿⣿⣿⣿⣦⠀⠈⢿⣿⣿⣾⡟⠀⣀⢼⠟⣿⣄⡀⠹⣷⣿⣿⡿⡇⠀⢀⣾⣿⣿⣿⣿⣿⣷⡄⠀⢹⣿⣿⣿⣿⣿⣿⣁⢸⣿⣟⠟⢳
⢸⣿⠃⢠⢽⣽⢿⣿⣿⣿⡇⠄⠀⣿⣿⣿⡁⠈⣿⣿⣿⡆⠀⢘⣿⣿⡿⠛⠛⢛⣉⡉⣉⡛⠛⠛⢿⣿⣿⡇⠧⠀⢸⣻⣿⣏⠀⣹⣿⣿⡧⠀⢸⣿⣿⣿⣿⢟⡟⠉⠉⣿⣯⠀⣸
⢸⣿⠠⠆⢨⣻⣿⣟⢿⣿⣿⡀⠀⢻⣿⣿⣿⣿⣿⣿⡟⠀⠀⣼⣿⣿⣿⢶⣛⣿⣷⣖⣶⣿⣟⣷⢾⣿⣿⣷⡀⠀⠘⢿⣿⣿⣿⣿⣿⣿⠃⠀⣾⣿⣿⣿⠿⣫⠠⠂⠀⢹⣿⢀⡇
⣿⡏⢰⠀⠀⠙⠶⠶⠾⣿⣿⣷⣄⠀⠉⠛⠻⠟⠛⠉⠀⣠⣾⣿⣿⣿⠟⠛⣉⣩⡀⠀⢀⣨⣉⡛⡿⣿⣿⣿⣷⣄⠀⠈⠙⠛⠿⠟⠋⠁⣠⣾⣿⣿⡿⠷⠾⠟⠁⠀⠀⢸⣿⡾⢠
⣿⣇⢨⣇⠀⠀⠀⠈⡻⠶⢭⣿⣿⣿⣶⣦⣤⣤⣤⣶⣾⣿⣿⢿⣿⡟⡆⣸⣿⡿⠃⠀⠈⠻⣿⣷⠀⠹⣿⢿⣿⣿⣿⣶⣦⣤⣤⣴⣶⣿⣿⣿⡯⠷⣟⠃⠀⠀⠀⢰⡇⢰⣿⠀⡊
⢹⣿⡸⣿⣆⠀⡀⠀⠺⢶⣖⣲⣤⣤⣼⣿⣿⣿⣿⣿⡿⣿⣟⡍⣿⡛⢰⣿⡟⠀⠀⠀⠀⠀⠹⣿⣧⢦⣻⣎⡈⠙⢿⣿⣿⣿⣿⣿⣽⣤⣤⡴⣲⠞⢃⣄⠀⠀⢠⡿⠁⣼⡿⢸⢹
⣷⣿⣿⡷⡉⡻⣿⣿⡆⠀⠀⠈⠉⠁⠀⠀⢋⣉⣠⣶⠿⠟⢉⡼⠓⠁⣾⡟⠀⠀⠀⠀⠀⠀⠀⠹⣿⡄⠉⢿⣌⠻⠷⢦⣬⣉⡙⠁⠀⠁⠉⠉⣤⠔⢉⣿⣿⠟⠋⢀⣼⣿⣷⢿⣸
⠈⠙⠿⣿⣷⡜⣜⣿⣿⢦⣤⣤⣀⣠⣴⣶⠿⠟⠋⠀⠀⠀⠋⠀⠀⢸⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⠈⠛⠛⠀⠀⠀⠉⠛⢿⣷⣦⣤⣀⡄⣠⣠⣾⣿⡇⠀⢠⣾⡿⠛⠙⢸⣼
⠀⠀⠀⢻⣿⣿⡄⣿⣿⡻⣯⣿⣿⠟⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠿⣿⣿⡋⠀⣿⣿⢁⣴⣿⣿⠁⠀⠀⣹⢸
⠀⠀⠀⠸⣿⡿⣿⡹⣿⣷⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣾⣿⠟⣼⡿⣿⡏⠀⠀⠀⢸⢻
⠤⣄⣄⡀⢻⣿⠈⢷⣀⠙⣿⣿⣿⣶⣤⣤⣄⣀⣀⣀⣀⣀⣀⣤⣤⣤⣶⣶⣾⣷⣦⣀⣤⣾⣷⣶⣶⣦⣤⣤⣀⣀⣀⣀⣀⣀⣀⣤⣤⣶⣾⣿⣿⠟⣡⡼⠏⣸⣿⢀⣀⣤⣤⣾⣻
⠁⠈⠛⠙⢸⣿⡄⣎⡇⢳⣞⣿⣟⡟⠻⡟⢿⣿⣿⣿⣿⣿⣿⣷⣶⣾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢻⡿⢛⢿⣿⡏⡰⢻⡇⣀⣿⡟⠉⢹⣿⡟⠙⠉
⠀⠀⠀⠀⠠⢿⣷⢏⢧⠀⡎⣻⣿⣿⡄⣿⡀⢻⠁⠈⣿⠁⠙⣟⠁⠙⡿⠋⢻⡟⠛⢿⠟⠻⡿⠋⢻⡏⠀⢹⡏⠈⣻⠋⠈⣿⠁⣼⣄⣾⣿⡟⠀⠀⣾⠳⢻⣿⢡⠀⠈⢿⣷⡀⠀
⠀⠀⠀⢠⠇⠸⣿⡘⣏⣇⠸⢳⢿⣿⣿⣿⣧⣸⣧⢠⣿⡇⢸⣿⠀⢰⣧⠀⣸⡇⢠⣿⡄⢠⣧⠀⣸⣇⠀⣸⣷⢠⣿⡇⢰⣿⣼⣿⣿⣿⣿⠃⠀⣸⠃⠀⣾⡿⠈⣆⠀⠈⠻⣿⣦
⠀⢀⣾⠏⠀⠀⣿⣇⢸⣾⠀⡏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⣿⣿⣦⣿⣷⣸⣿⣷⣼⣿⣧⣿⣿⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⢀⡿⠀⢰⣿⠇⠀⠘⣷⣄⡀⠈⠙
⢔⡽⠃⠀⠀⢠⢻⣿⠈⡟⢢⢸⣼⣿⣿⣿⣿⣏⣿⠹⣿⢻⣿⢻⣿⢿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⡟⢿⡏⢻⢏⣷⣿⣿⣿⠇⢰⢸⠃⠀⣸⣿⢦⠀⠀⠈⠻⣿⣶⡤
⠀⠀⠀⠀⣰⠏⠈⢿⣧⡸⡸⣟⣇⢹⣿⣿⣿⣿⣿⣶⣧⣠⣯⣀⣿⢘⡏⠘⡟⢻⡟⣿⠋⣿⢹⡏⢘⣇⣸⣇⣸⣅⣸⣷⣾⣿⣿⣿⣿⡿⢀⡿⠀⠀⣴⣿⠇⠘⣷⡀⠀⠀⠈⠙⠻
⠀⠀⣠⣾⡏⠀⠀⠈⢻⣷⡕⢎⢹⣯⡛⢿⣿⣿⣿⣿⣿⡿⠿⣿⣿⣿⣿⣾⣿⣾⣷⣿⣶⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠁⡾⠁⢀⣼⡿⠃⠀⠀⠙⣿⣦⠀⠀⠀⠀
⠀⢞⣿⠏⠀⠀⠀⠀⠀⠹⣿⣝⢆⠹⢇⠀⠉⠛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠋⠁⣠⡾⠁⢠⣾⡿⠁⠀⠀⠀⠀⠹⣿⣷⣦⡀⠀
⠚⠋⠋⠀⠀⠀⠀⠀⠀⠀⢻⣿⣯⡳⡄⠕⠂⠀⠀⠀⠀⠉⠉⠛⠛⠛⠛⠛⠛⠛⠿⠿⠿⠟⠛⠛⠛⠛⠛⠛⠋⠉⠁⠀⠀⠀⠤⠚⠋⡴⣱⣿⢿⠁⠀⠀⠀⠀⠀⠀⢈⡿⠿⣿⣦
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⣯⢻⣷⣍⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡿⢻⣇⠀⠀⠀⠀⠀⠀⠀⠩⢒⠀⠀⠉
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡟⡎⢻⣿⣦⡀⠀⠀⠀⢀⣤⡤⠖⢚⣃⣀⡤⠄⠀⠀⠀⠀⠀⠀⢤⣄⣈⣓⠒⠤⣤⣀⠀⠀⠀⢀⣰⣿⣿⢃⣾⡏⠀⠀⠀⠀⠀⠀⠀⠐⠉⠀⠀⠀
⣍⠉⠛⠿⠷⣶⣶⣶⣶⣟⠯⠅⠸⣌⢿⣻⣿⡟⠓⠛⠋⠁⠒⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠓⠈⠉⠛⠛⢛⣿⣿⣿⣁⠞⢀⠥⣒⣶⣶⣶⣶⠾⠿⠟⠋⢁⣴⡾
⠛⢷⣤⡀⡀⠀⠀⠀⠀⠀⠀⠀⠐⣼⡷⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⡿⣷⣟⠀⠐⠃⠀⠀⠀⠀⠀⠠⢒⣠⣾⠟⠁⠀
⠀⠀⢉⡻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠘⢿⣳⣿⣿⣿⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⡿⡟⡽⠋⠀⠀⠀⠀⠀⠀⠀⣀⣴⠟⣋⠴⣪⠄⠀
⡄⠀⣠⢌⢷⢟⠻⢷⣦⢤⣀⠀⠀⠀⠀⠙⣿⣿⣮⢿⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡿⣫⣿⣿⠟⠁⠀⠀⠀⢀⡠⣴⣾⠿⢋⡠⣚⣵⡮⠖⣾⡋
⣇⠀⢈⣵⣶⣭⣛⠀⠙⣛⢾⣿⣖⣦⣀⡀⢘⣿⣿⣧⢻⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡿⣱⣿⣿⡋⠀⣀⣤⣶⣾⡿⠞⠋⡠⠖⣥⣾⣧⣅⠀⣠⣿⣿
⣿⣿⡿⠭⠤⢹⣷⢈⡙⠂⠈⠓⠽⣮⠽⣿⠿⣿⣿⡝⣷⡹⣿⣅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡟⣽⢯⣾⣿⡿⣿⡿⢁⠋⠁⠀⠀⠁⡀⢸⣟⠀⠬⣿⣿⣿⣿⣿
⣿⣾⣿⣧⣶⣟⣵⢶⣍⠲⢤⣀⠀⠈⠁⠠⠙⠺⣿⡃⠈⢳⡝⠻⢿⣶⣶⣤⣤⣤⣤⣀⣠⣤⣤⣤⣴⣶⣿⠿⢋⡾⠋⢨⣿⠿⠋⠥⠚⠁⠀⢀⣤⠖⣋⣵⢶⣝⣷⣜⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣶⣿⠁⠉⠳⠿⣦⣄⡀⠀⠀⠀⠉⠳⢦⡹⣄⠀⠀⢻⣏⠙⠛⠛⠛⠛⠛⠋⣩⡿⠁⠀⢠⠟⣠⠾⠋⠊⠀⠊⠀⣠⣴⠾⠗⠋⠀⣿⣧⣺⣿⣿⣿⣿⣿⣿⣿⣿
*/
#include <bits/stdc++.h>
using namespace std;
#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define ell cerr << "\n=========================================\n"
#define el cerr << '\n'
#define Unique(v) v.erase(unique(alll(v)), v.end())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
template<int D, typename T> struct Vec : public vector<Vec<D - 1, T>> { template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {} };
template<typename T> struct Vec<1, T> : public vector<T> { Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {} };
const int INF = 1e13;
void ivan()
{
int n, m, k;
cin >> n >> m >> k;
Vec<2, int> d(n + 1, n + 1, INF), b(n + 1, k + 1, INF), s(n + 1, k + 1, INF), p(n + 1, n + 1);
fore(i, 1, n)
fore(j, 1, k) cin >> b[i][j] >> s[i][j];
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
}
fore(k, 1, n) fore(i, 1, n) fore(j, 1, n)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
fore(i, 1, n) fore(j, 1, n) fore(x, 1, k)
if (b[i][x] != -1 && s[j][x] != -1)
p[i][j] = max(p[i][j], s[j][x] - b[i][x]);
// fore(i, 1, n) fore(j, 1, n) db(i), db(j), db(p[i][j]), el;
auto check = [&](int mid) -> bool
{
Vec<2, int> f(n + 1, n + 1, INF);
fore(i, 1, n) fore(j, 1, n) f[i][j] = mid * d[i][j] - p[i][j];
fore(k, 1, n) fore(i, 1, n) fore(j, 1, n)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
fore(i, 1, n) if (f[i][i] <= 0) return 1;
return 0;
};
int l = 1, r = 1e9, ans = -1;
while (l <= r)
{
int m = (l + r) >> 1;
if (check(m)) l = m + 1, ans = m;
else r = m - 1;
}
cout << ans;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
if (fopen("in", "r")) freopen("in", "r", stdin);
if (fopen(TASKNAME".inp", "r"))
{
freopen(TASKNAME".inp", "r", stdin);
freopen(TASKNAME".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while (tc--) ivan();
ell, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", ell;
return 0;
}
