Submission #1225277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225277		marselel	Art Exhibition (JOI18_art)	C++20	100 / 100	122 ms	19792 KiB

art

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define all(a) a.begin(), a.end()
using namespace std;


/*
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⣀⣴⣿⠽⠿⣟⣛⣦⡶⣄⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⣴⡶⣛⡭⣖⣾⣿⣿⣿⣿⣿⣿⣿⣿⣯⡻⣦⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡶⣫⣾⢟⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣲⣝⢿⣤⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⣴⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣽⣯⢿⣮⡻⣦⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣠⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣟⣿⣿⣿⣿⣿⣿⣿⡽⣿⣿⣿⣻⣯⣿⣷⠻⣦⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡴⣼⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣼⣿⣿⣿⣿⡏⡯⣿⣿⣿⣽⣿⣿⣿⣾⣯⢿⣿⣮⢿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡼⣰⠙⢾⢻⣿⣿⠿⣿⣽⣿⠿⢣⢳⣿⣿⣿⣿⣏⡇⣿⣿⣿⣿⣿⣿⢟⣯⡽⣿⣿⡿⣷⡻⡄⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣼⡀⢧⡀⡀⠙⢯⠁⣼⡿⢄⢀⣟⣿⠘⣿⣿⢿⣿⣹⣯⢿⣿⢸⠘⡷⣋⢱⡺⠹⣹⢉⣽⠙⡃⠹⣄⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢠⠁⡞⠳⣏⡢⡀⡀⠉⢿⣴⢷⣿⣿⡇⡕⠢⣰⣿⠃⣿⣿⠘⠛⣿⠈⠘⡘⠪⣩⠶⢻⢢⣄⣧⢑⣀⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠏⣷⣦⣄⡀⠈⠓⣷⣄⣀⠙⣿⠋⣿⠁⣶⣿⣳⣿⢼⣿⣿⡀⡄⣿⢸⣻⢷⠉⡀⡀⡀⣆⡮⢌⡞⣿⠘⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡾⣼⡏⣿⣷⣭⡳⣤⡀⠈⢛⠶⡉⠓⣿⢾⣿⡟⣿⣟⣿⣃⣿⡯⣳⡿⡇⣾⢆⣆⡀⡀⡀⠘⣈⡶⡽⣿⡇⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢠⢡⣇⠁⣿⣿⣿⣿⣵⠿⣛⣉⡀⡀⡀⣿⣺⣿⣾⣿⣿⡿⡄⣿⣿⣿⠓⡿⣸⢯⡸⡀⢀⡴⣋⢻⢿⣯⣿⣿⢿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡞⣿⢸⢸⣿⣿⣿⣿⣾⡿⠋⣿⣿⣦⡀⢿⡯⣱⡟⢸⡿⡰⡀⢸⣿⣿⡀⢹⣧⣙⡴⢿⢱⡳⡣⢌⣿⣿⣿⣿⢸⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢰⢡⡿⣿⣼⣿⣿⣿⢣⣿⡀⢀⢀⣿⣛⠻⠘⣿⡿⡘⣸⣴⣶⣿⣾⣶⣿⣦⡀⡿⡇⣿⣿⡆⣇⣕⢫⢹⣿⣿⣿⡘⣧⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣾⢻⡿⣿⣿⣿⣿⡾⢻⡀⣿⡀⣿⡾⡀⡀⣿⡰⡀⡀⡀⡀⢻⣿⡿⠿⡿⣆⢸⣸⢧⢷⡼⡩⡳⡫⠅⣧⣿⣿⡇⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⡇⣿⣿⣷⣿⣿⣿⡏⡇⡇⠄⢿⡀⠙⡀⡀⠠⠡⡀⡀⡀⢰⠉⢹⣿⡷⣶⡀⡿⡏⣿⣿⣿⣿⢷⣥⢞⡇⣧⣿⣿⡇⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⢹⡏⣿⣿⣿⣿⣿⢸⣇⡇⠐⠠⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⡀⠈⠛⢠⠋⡼⢰⣸⣻⣿⣿⣿⣿⣾⣿⡑⡟⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢠⢰⢼⢽⣿⣿⣿⣿⣿⣾⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡉⠓⠲⡀⡀⡀⡿⣿⣿⣿⣿⣿⡏⡏⣿⡀⡇⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣸⣿⣿⣿⡿⣿⣿⣿⣿⣿⣧⡀⡀⡀⡀⡀⡀⣀⣀⡀⡀⡀⡀⡀⠈⡀⠁⡀⢰⡽⣟⣿⣿⡏⡏⣾⣼⣿⢸⢳⣿⣿⣻⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣯⣟⣿⡏⡇⣿⣿⣷⡀⡀⡀⡀⣿⠛⢩⢍⡿⡀⡀⡀⡀⡀⡀⡀⢯⣾⣾⣿⡿⣸⣱⢧⣿⡿⣿⣼⣿⡯⣹⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣏⣿⣿⣿⡯⣿⡇⡇⣿⣿⣿⣿⣆⡀⡀⠈⠦⠬⠞⡀⡀⡀⡀⡀⡀⡀⣼⣼⣯⣿⣿⣹⣏⣿⣺⣿⣾⡟⣿⣿⣱⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠸⢸⢸⣿⣿⣿⣿⣿⢥⠁⣿⣿⣿⣿⡿⣿⣄⡀⡀⡀⡀⡀⡀⣀⡠⣴⣾⣿⣱⣯⣿⣿⣣⣿⢿⢏⣿⣹⣿⣸⣏⢏⡿⡟⡿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠸⢸⣿⣿⣿⣿⣿⣼⡇⠘⣿⣿⣿⡇⣿⣿⢹⠶⠒⡛⡉⢠⡆⢸⣿⣿⣿⣟⣿⣿⢏⣿⣟⡿⣿⢯⣿⡟⣿⣾⣿⣿⢸⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⢸⣿⣿⢽⣿⡷⠲⣌⣿⣿⡇⡈⣿⠏⡎⢕⡢⢌⡸⠇⣿⣿⣿⣟⣿⣿⣟⣿⣟⣿⣾⡟⣿⡿⣿⢫⣿⡟⠃⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⢸⣿⣿⣝⣿⡇⡀⡀⡀⣶⠒⠲⡿⡰⢎⡸⡃⡠⡅⠄⡇⢉⣿⣿⣿⢟⣿⢿⣿⣹⡿⣾⡟⡏⡟⣿⣿⠘⢀⡿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢹⣟⣨⣺⣿⡇⣿⣿⡀⡀⡀⢸⡟⢉⢄⡊⢔⡢⠢⠢⠪⢅⢳⡿⣾⣿⢏⣿⠏⢻⢳⣿⣽⣿⡀⢯⣾⣿⡏⡀⣼⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⣻⣃⣿⡏⣿⣿⣧⣷⠦⣀⡀⣷⠰⠕⠨⢅⢢⢜⢎⢌⠅⣾⣾⣿⣱⡿⠏⣼⡿⣿⣽⡟⡀⢰⣸⣿⡟⡀⠠⠏⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣰⣿⣾⣿⣇⣿⣿⡇⣿⡀⣇⢷⣹⠲⣌⡊⢑⡑⡑⠑⣁⡾⣿⢟⣾⡟⡜⡀⢡⣻⣵⡿⣴⣯⡏⣿⡟⣭⣿⣽⠟⣦⣀⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⣟⣿⣿⡟⣧⡸⣿⣇⣿⢰⢵⣿⡻⣄⡀⠘⠉⡉⠉⠛⣴⡽⣵⣿⠋⡼⡀⡀⡟⣿⣫⢟⣥⢴⢿⣟⠿⣷⣭⣿⣯⣶⣾⢒⡟⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣾⣾⣿⡟⡀⣿⡀⢿⣿⢿⢏⣿⣿⣿⣜⣖⣛⣽⣬⠷⣶⣡⣿⡿⡀⡼⡀⡀⣸⡾⣱⣃⡴⡀⡏⡟⢀⡷⣽⣿⣿⣿⡟⣵⢻⡆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⢟⣿⣿⡟⡀⡀⠈⡀⡀⣼⣿⣿⣿⣿⣿⣿⢸⢳⠷⣹⣿⣿⣿⣏⡀⡼⡀⡀⡀⢗⣾⣹⣋⣤⣤⣞⡶⣫⣿⣿⣿⡿⣵⠛⢿⢻⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣰⠃⠉⢛⡟⡀⡀⡀⡀⡀⣰⣿⣿⣧⢿⣿⣿⣿⣧⣟⣭⣱⣡⣻⣿⣿⡿⡀⡀⢀⣾⣯⣯⣯⣷⣿⣯⣿⣿⣿⣿⣿⣫⡋⠹⣷⡀⣧⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡿⣦⣀⡿⡀⡀⡀⡀⡀⡀⣿⣿⣿⡇⡻⣶⣭⣛⣿⣜⣵⣫⣵⣬⣬⡷⡀⢀⣴⢯⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⡾⠁⠘⡀⢻⣧⢸⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣾⡀⢙⡿⡀⡀⡀⡀⡀⡀⣸⣿⣿⢵⢿⣝⣯⣷⡈⣷⡻⣎⣾⣿⣿⡟⡀⣴⣿⠟⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⡫⢯⠁⡠⡅⢻⠈⣿⡀⡏⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⡷⡿⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣷⢧⣝⡹⣿⣿⣿⣮⠿⣏⣯⣴⣿⠿⠁⡿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣾⢐⠂⠇⢀⡇⣿⣸⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣸⡾⡀⡀⡀⡀⡀⡀⡀⢰⣿⣿⣿⢽⣿⣷⢿⣃⣇⣿⢻⣿⣿⣛⣷⠟⣡⡶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠈⣤⠛⡀⣿⣿⣾⡀⡆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⣿⡀⡀⡀⡀⡀⡀⡀⠠⣿⣼⣿⡿⣯⣿⣿⣷⢷⠘⢾⣿⣿⠿⣉⣴⣫⣾⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡻⣞⡀⠂⡀⣼⣵⠋⠠⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡀⡀⡀⡀⡀⡀⡀⡀⢁⣏⣿⡿⣿⣿⢽⣿⣻⣷⢻⣘⣿⣴⣿⣿⣟⣿⡿⣽⣿⣯⣿⢟⣿⣿⣿⣿⣿⣿⡟⡻⣿⣿⣭⢶⠉⢻⣿⣧⡀⡀⢿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣼⠁⡀⡀⡀⡀⡀⡀⡀⡸⣼⣺⣿⣿⣻⣿⣿⣿⣯⣿⢸⢿⣿⣿⡿⣿⣾⡿⣽⣽⣾⣿⣿⣸⢽⣿⣿⡿⣿⣿⣷⣿⣝⣿⣿⣷⢻⣿⣿⣾⡀⡀⠘⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣰⠃⡀⡀⡀⡀⡀⡀⡀⢀⡀⡟⣿⣿⣿⣿⢿⣿⣝⢿⢿⡹⠽⣿⡿⣾⣼⣿⣿⡿⣾⣽⣿⢣⢻⣺⣿⣿⣹⡹⣿⣿⣷⣿⢮⢿⣿⣷⢿⣿⣷⡇⡀⡀⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⠃⡀⡀⡀⡀⡀⡀⡀⡀⠎⣸⢹⣿⣿⣿⣿⣷⣿⣿⡺⣮⢕⠈⠛⣿⣞⡿⣽⣿⣱⣣⣿⢏⣟⢸⣽⣿⢇⡿⡇⣿⣿⣿⣿⣿⡿⡻⣿⣷⢻⣿⢿⡀⡀⢿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡟⡀⡀⡀⡀⡀⡀⡀⡀⡰⡀⣿⢸⣿⣿⣿⡿⣛⡾⢿⣿⢿⢣⢀⡟⣷⣿⣿⣿⢱⣯⣿⣏⡿⣮⣿⣿⣿⣾⢣⣿⣿⡿⣿⣿⣿⣾⣿⣎⣿⣯⡻⣿⡀⡀⢸⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠇⡀⡀⡀⡀⡀⡀⡀⢀⠁⣸⢀⡆⣿⣿⢵⣏⡀⣀⣤⠿⣿⣸⣏⢽⡟⣻⣭⣾⣿⣿⡿⣿⣟⡇⡧⣿⢣⡿⣿⣿⢻⣏⣿⣿⣿⣿⣿⣿⣯⡻⣿⡝⣆⡀⡀⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡃⡀⡿⢸⣿⢿⣿⣿⣿⣿⡀⡀⣠⠃⠙⠻⠿⣿⠿⣿⣯⡿⣿⣱⡏⣿⢺⢼⣿⣺⢽⣯⣿⣜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣮⢻⣿⡀⡀⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡇⡀⡀⡀⡀⡀⡰⠑⠅⣰⡀⡀⢸⣮⣿⣿⣿⣼⡄⣴⠁⡀⢀⡀⣇⡀⢳⢻⡏⡯⢏⣿⢆⢽⣾⣾⣿⣿⣿⣿⣿⣷⣿⢿⣿⣟⣿⡯⠿⠗⠛⠉⠙⠾⡀⡀⢸⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢻⡀⡀⡀⡤⠑⢨⠂⣴⠁⡀⡀⢸⣿⣿⣿⣿⡟⡞⣿⡀⠁⢸⡀⢹⡀⠘⣺⣿⢸⡟⡏⢽⢼⣿⣿⡇⣷⣿⣿⣿⣿⣚⢸⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣠⠒⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠷⡐⠅⡀⠐⣠⠞⡀⡀⡀⡀⣿⣿⣿⣿⣟⡿⡗⡟⡀⣠⢾⣤⢻⢷⡀⡗⣷⣿⡇⣗⢹⣿⣿⣿⢇⡗⣿⣿⣿⣿⡿⣷⠁⡀⡀⣀⣀⣠⡤⠶⠒⠋⠉⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⠈⠳⡤⠟⠁⡀⡀⡀⡀⡀⡯⣿⣿⢯⢿⣿⡇⡧⣿⣾⣿⣿⢝⢾⣽⣿⣿⣿⣧⢯⣸⣿⢹⡹⣾⣼⣿⣿⣿⣿⡏⠉⠉⠉⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀
*/

struct Jar{
    ll a, b;
};

void solve(){
    ll n; cin >> n;
    vector<Jar> a(n);
    for (auto &[a1, b1]: a)cin >> a1 >> b1;

    sort(all(a), [](Jar x, Jar y){
        return x.a < y.a || (x.a == y.a && x.b < y.b);
    });
    ll ben = 0;
    for (int i = 0; i < n; ++i){
        ben += a[i].b;
    }
    ben -= (a.back().a - a.front().a);
    vector<ll> forw(n);
    vector<ll> back(n);
    for (int i = 0; i < n - 1; ++i){
        forw[i] = a[i + 1].a - a[i].a - a[i].b;
    }
    for (int i = n - 1; i > 0; --i){
        back[i] = a[i].a - a[i - 1].a - a[i].b;
        if (i != n - 1)back[i] += back[i + 1];
    }
    vector<ll> maxi(n + 1, INT_MAX);
    maxi[n - 1] = max(0LL, back[n - 1]);
    for (int i = n - 2; i >= 0; --i){
        maxi[i] = max(maxi[i + 1], back[i]);
    }
    maxi[n] = 0;
    ll ans = max(ben, ben + maxi[1]);
    ll val = 0;
    for (int i = 0; i < n - 1; ++i){
        val += forw[i];
        ans = max(ans, ben + val + maxi[i + 2]);
    }
    cout<<ans;



}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int tt = 1;
    while (tt--)solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50