class CloudStorage:
    ADMIN = "admin"

    def __init__(self):
        self.files = {}
        self.users = {self.ADMIN: {"cap": float('inf'), "used": 0}}
        self.backups = {}

    def addFile(self, name, capacity):
        if name in self.files:
            return False
        self.files[name] = {"size": capacity, "owner": self.ADMIN}
        self.users[self.ADMIN]["used"] += capacity
        return True

    def getFileSize(self, name):
        return self.files[name]["size"] if name in self.files else None

    def deleteFile(self, name):
        if name not in self.files:
            return None
        size = self.files[name]["size"]
        owner = self.files[name]["owner"]
        self.users[owner]["used"] -= size
        del self.files[name]
        return size

    def getNFilesByPrefix(self, prefix, n):
        matched = [(name, info["size"]) for name, info in self.files.items() if name.startswith(prefix)]
        matched.sort(key=lambda x: (-x[1], x[0]))
        return [f"{name}({size})" for name, size in matched[:n]]

    def addUser(self, userId, capacity):
        if userId in self.users:
            return False
        self.users[userId] = {"cap": capacity, "used": 0}
        return True

    def addFileBy(self, userId, name, size):
        if userId not in self.users or name in self.files:
            return None
        u = self.users[userId]
        if u["used"] + size > u["cap"]:
            return None
        self.files[name] = {"size": size, "owner": userId}
        u["used"] += size
        return u["cap"] - u["used"]

    def mergeUser(self, u1, u2):
        if u1 == u2 or u1 not in self.users or u2 not in self.users:
            return None
        for name, info in self.files.items():
            if info["owner"] == u2:
                info["owner"] = u1
        self.users[u1]["cap"] += self.users[u2]["cap"] - self.users[u2]["used"]
        self.users[u1]["used"] += self.users[u2]["used"]
        del self.users[u2]
        self.backups.pop(u2, None)
        return self.users[u1]["cap"]

    def backupUser(self, userId):
        if userId not in self.users:
            return None
        snap = {name: info["size"] for name, info in self.files.items() if info["owner"] == userId}
        self.backups[userId] = snap
        return len(snap)

    def restoreUser(self, userId):
        if userId not in self.users:
            return None
        to_del = [n for n, info in self.files.items() if info["owner"] == userId]
        for n in to_del:
            self.users[userId]["used"] -= self.files[n]["size"]
            del self.files[n]
        snap = self.backups.get(userId)
        if snap is None:
            return 0
        restored = 0
        u = self.users[userId]
        for n, size in snap.items():
            if n in self.files:
                continue
            if u["used"] + size > u["cap"]:
                continue
            self.files[n] = {"size": size, "owner": userId}
            u["used"] += size
            restored += 1
        return restored

import java.util.*;

class CloudStorage {
    static final String ADMIN = "admin";

    static class FileInfo { int size; String owner; FileInfo(int s, String o){ size=s; owner=o; } }
    static class User { long cap; long used; User(long c){ cap=c; used=0; } }

    Map<String, FileInfo> files = new HashMap<>();
    Map<String, User> users = new HashMap<>();
    Map<String, Map<String, Integer>> backups = new HashMap<>();

    CloudStorage() { users.put(ADMIN, new User(Long.MAX_VALUE)); }

    public boolean addFile(String name, int capacity) {
        if (files.containsKey(name)) return false;
        files.put(name, new FileInfo(capacity, ADMIN));
        users.get(ADMIN).used += capacity;
        return true;
    }
    public Optional<Integer> getFileSize(String name) {
        return files.containsKey(name) ? Optional.of(files.get(name).size) : Optional.empty();
    }
    public Optional<Integer> deleteFile(String name) {
        FileInfo f = files.remove(name);
        if (f == null) return Optional.empty();
        users.get(f.owner).used -= f.size;
        return Optional.of(f.size);
    }
    public List<String> getNFilesByPrefix(String prefix, int n) {
        List<Map.Entry<String, FileInfo>> matched = new ArrayList<>();
        for (var e : files.entrySet()) if (e.getKey().startsWith(prefix)) matched.add(e);
        matched.sort((a, b) -> a.getValue().size != b.getValue().size
                ? Integer.compare(b.getValue().size, a.getValue().size)
                : a.getKey().compareTo(b.getKey()));
        List<String> out = new ArrayList<>();
        for (int i = 0; i < Math.min(n, matched.size()); i++)
            out.add(matched.get(i).getKey() + "(" + matched.get(i).getValue().size + ")");
        return out;
    }
    public boolean addUser(String userId, int capacity) {
        if (users.containsKey(userId)) return false;
        users.put(userId, new User(capacity));
        return true;
    }
    public Optional<Long> addFileBy(String userId, String name, int size) {
        if (!users.containsKey(userId) || files.containsKey(name)) return Optional.empty();
        User u = users.get(userId);
        if (u.used + size > u.cap) return Optional.empty();
        files.put(name, new FileInfo(size, userId));
        u.used += size;
        return Optional.of(u.cap - u.used);
    }
    public Optional<Long> mergeUser(String u1, String u2) {
        if (u1.equals(u2) || !users.containsKey(u1) || !users.containsKey(u2)) return Optional.empty();
        for (FileInfo f : files.values()) if (f.owner.equals(u2)) f.owner = u1;
        users.get(u1).cap += users.get(u2).cap - users.get(u2).used;
        users.get(u1).used += users.get(u2).used;
        users.remove(u2);
        backups.remove(u2);
        return Optional.of(users.get(u1).cap);
    }
    public Optional<Integer> backupUser(String userId) {
        if (!users.containsKey(userId)) return Optional.empty();
        Map<String, Integer> snap = new HashMap<>();
        for (var e : files.entrySet())
            if (e.getValue().owner.equals(userId)) snap.put(e.getKey(), e.getValue().size);
        backups.put(userId, snap);
        return Optional.of(snap.size());
    }
    public Optional<Integer> restoreUser(String userId) {
        if (!users.containsKey(userId)) return Optional.empty();
        List<String> toDel = new ArrayList<>();
        for (var e : files.entrySet()) if (e.getValue().owner.equals(userId)) toDel.add(e.getKey());
        for (String n : toDel) { users.get(userId).used -= files.get(n).size; files.remove(n); }
        Map<String, Integer> snap = backups.get(userId);
        if (snap == null) return Optional.of(0);
        int restored = 0;
        User u = users.get(userId);
        for (var e : snap.entrySet()) {
            if (files.containsKey(e.getKey())) continue;
            if (u.used + e.getValue() > u.cap) continue;
            files.put(e.getKey(), new FileInfo(e.getValue(), userId));
            u.used += e.getValue();
            restored++;
        }
        return Optional.of(restored);
    }
}

#include <unordered_map>
#include <string>
#include <vector>
#include <optional>
#include <algorithm>
#include <climits>
using namespace std;

class CloudStorage {
    struct FileInfo { long long size; string owner; };
    struct User { long long cap; long long used; };
    unordered_map<string, FileInfo> files;
    unordered_map<string, User> users;
    unordered_map<string, unordered_map<string, long long>> backups;
    static constexpr long long INF = LLONG_MAX / 4;
public:
    CloudStorage() { users["admin"] = {INF, 0}; }

    bool addFile(const string& name, long long cap) {
        if (files.count(name)) return false;
        files[name] = {cap, "admin"};
        users["admin"].used += cap;
        return true;
    }
    optional<long long> getFileSize(const string& name) {
        auto it = files.find(name);
        return it == files.end() ? nullopt : optional<long long>(it->second.size);
    }
    optional<long long> deleteFile(const string& name) {
        auto it = files.find(name);
        if (it == files.end()) return nullopt;
        long long s = it->second.size;
        users[it->second.owner].used -= s;
        files.erase(it);
        return s;
    }
    vector<string> getNFilesByPrefix(const string& prefix, int n) {
        vector<pair<string, long long>> matched;
        for (auto& [k, v] : files)
            if (k.rfind(prefix, 0) == 0) matched.push_back({k, v.size});
        sort(matched.begin(), matched.end(), [](auto& a, auto& b){
            return a.second != b.second ? a.second > b.second : a.first < b.first;
        });
        vector<string> out;
        for (int i = 0; i < (int)min<size_t>(n, matched.size()); i++)
            out.push_back(matched[i].first + "(" + to_string(matched[i].second) + ")");
        return out;
    }
    bool addUser(const string& id, long long cap) {
        if (users.count(id)) return false;
        users[id] = {cap, 0};
        return true;
    }
    optional<long long> addFileBy(const string& id, const string& name, long long size) {
        if (!users.count(id) || files.count(name)) return nullopt;
        auto& u = users[id];
        if (u.used + size > u.cap) return nullopt;
        files[name] = {size, id};
        u.used += size;
        return u.cap - u.used;
    }
    optional<long long> mergeUser(const string& a, const string& b) {
        if (a == b || !users.count(a) || !users.count(b)) return nullopt;
        for (auto& [_, f] : files) if (f.owner == b) f.owner = a;
        users[a].cap += users[b].cap - users[b].used;
        users[a].used += users[b].used;
        users.erase(b);
        backups.erase(b);
        return users[a].cap;
    }
    optional<long long> backupUser(const string& id) {
        if (!users.count(id)) return nullopt;
        unordered_map<string, long long> snap;
        for (auto& [k, v] : files) if (v.owner == id) snap[k] = v.size;
        backups[id] = snap;
        return (long long)snap.size();
    }
    optional<long long> restoreUser(const string& id) {
        if (!users.count(id)) return nullopt;
        vector<string> del;
        for (auto& [k, v] : files) if (v.owner == id) del.push_back(k);
        for (auto& k : del) { users[id].used -= files[k].size; files.erase(k); }
        auto it = backups.find(id);
        if (it == backups.end()) return 0LL;
        long long restored = 0;
        auto& u = users[id];
        for (auto& [k, sz] : it->second) {
            if (files.count(k)) continue;
            if (u.used + sz > u.cap) continue;
            files[k] = {sz, id};
            u.used += sz;
            restored++;
        }
        return restored;
    }
};

from typing import List

def count_single_coverage(light_sources: List[List[int]]) -> int:
    events = []
    for c, r in light_sources:
        events.append((c - r, 1))
        events.append((c + r + 1, -1))
    events.sort()
    cnt = 0
    total = 0
    prev = None
    for x, delta in events:
        if prev is not None and cnt == 1:
            total += x - prev
        cnt += delta
        prev = x
    return total

import java.util.*;

class Solution {
    public long countSingleCoverage(int[][] lightSources) {
        List<int[]> events = new ArrayList<>();
        for (int[] s : lightSources) {
            events.add(new int[]{s[0] - s[1], 1});
            events.add(new int[]{s[0] + s[1] + 1, -1});
        }
        events.sort((a, b) -> a[0] - b[0]);
        long total = 0;
        int cnt = 0;
        Integer prev = null;
        for (int[] e : events) {
            if (prev != null && cnt == 1) total += e[0] - prev;
            cnt += e[1];
            prev = e[0];
        }
        return total;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long countSingleCoverage(vector<vector<int>>& lightSources) {
        vector<pair<int, int>> events;
        for (auto& s : lightSources) {
            events.push_back({s[0] - s[1], 1});
            events.push_back({s[0] + s[1] + 1, -1});
        }
        sort(events.begin(), events.end());
        long long total = 0;
        int cnt = 0;
        bool first = true;
        int prev = 0;
        for (auto& [x, d] : events) {
            if (!first && cnt == 1) total += x - prev;
            cnt += d;
            prev = x;
            first = false;
        }
        return total;
    }
};

from typing import List

def earn_the_most(prices: List[int], strategy: List[str], mrk: int) -> int:
    n = len(prices)
    base = 0
    for i in range(n):
        if strategy[i] == 'S': base += prices[i]
        elif strategy[i] == 'B': base -= prices[i]

    # contribution if window [i, i+mrk-1] is replaced: first mrk/2 H, last mrk/2 S
    h = mrk // 2
    best = base
    for i in range(n - mrk + 1):
        old = 0
        for j in range(mrk):
            if strategy[i + j] == 'S': old += prices[i + j]
            elif strategy[i + j] == 'B': old -= prices[i + j]
        new = sum(prices[i + h: i + mrk])
        best = max(best, base - old + new)
    return best

import java.util.*;

class Solution {
    public long earnTheMost(int[] prices, char[] strategy, int mrk) {
        int n = prices.length;
        long base = 0;
        for (int i = 0; i < n; i++) {
            if (strategy[i] == 'S') base += prices[i];
            else if (strategy[i] == 'B') base -= prices[i];
        }
        int h = mrk / 2;
        long best = base;
        for (int i = 0; i + mrk <= n; i++) {
            long old = 0, neu = 0;
            for (int j = 0; j < mrk; j++) {
                if (strategy[i + j] == 'S') old += prices[i + j];
                else if (strategy[i + j] == 'B') old -= prices[i + j];
                if (j >= h) neu += prices[i + j];
            }
            best = Math.max(best, base - old + neu);
        }
        return best;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long earnTheMost(vector<int>& prices, string strategy, int mrk) {
        int n = prices.size();
        long long base = 0;
        for (int i = 0; i < n; i++) {
            if (strategy[i] == 'S') base += prices[i];
            else if (strategy[i] == 'B') base -= prices[i];
        }
        int h = mrk / 2;
        long long best = base;
        for (int i = 0; i + mrk <= n; i++) {
            long long old = 0, neu = 0;
            for (int j = 0; j < mrk; j++) {
                if (strategy[i + j] == 'S') old += prices[i + j];
                else if (strategy[i + j] == 'B') old -= prices[i + j];
                if (j >= h) neu += prices[i + j];
            }
            best = max(best, base - old + neu);
        }
        return best;
    }
};