#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();
}
