#include <fstream>
#include <vector>
using namespace std;

int main() {
    ifstream we("dane.txt");
    vector<int> liczby;
    int x;
    while (we >> x)            // czyta, dopóki są liczby
        liczby.push_back(x);

    int parzyste = 0;
    for (int v : liczby)
        if (v % 2 == 0) parzyste++;

    ofstream wy("wyniki.txt");
    wy << "1.1. " << parzyste << "\n";
}

int suma_cyfr(long long n) {
    int s = 0;
    while (n > 0) {
        s += n % 10;      // ostatnia cyfra
        n /= 10;          // obcinamy ostatnią cyfrę
    }
    return s;
}

long long odwroc(long long n) {
    long long w = 0;
    while (n > 0) {
        w = w * 10 + n % 10;
        n /= 10;
    }
    return w;
}

#include <vector>
#include <algorithm>
using namespace std;

vector<long long> dzielniki(long long n) {
    vector<long long> wynik;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            wynik.push_back(d);
            if (d != n / d)          // para d i n/d, bez dublowania pierwiastka
                wynik.push_back(n / d);
        }
    }
    sort(wynik.begin(), wynik.end());
    return wynik;
}

bool doskonala(long long n) {
    long long s = 0;
    for (long long d : dzielniki(n)) s += d;
    return s - n == n;
}

long long tylko_nieparzyste(long long n) {   // 52318 -> 531: zostawia cyfry nieparzyste
    long long wynik = 0, mnoznik = 1;        // mnoznik: pozycja następnej cyfry
    while (n > 0) {
        int c = n % 10;
        if (c % 2 == 1) {
            wynik += c * mnoznik;
            mnoznik *= 10;
        }
        n /= 10;
    }
    return wynik;
}

long long dopelnienie(long long n) {         // każda cyfra c zamienia się na 9 - c
    long long wynik = 0, mnoznik = 1;
    do {
        wynik += (9 - n % 10) * mnoznik;
        mnoznik *= 10;
        n /= 10;
    } while (n > 0);
    return wynik;
}

int przeniesienia(long long a, long long b) {   // przeniesienia przy dodawaniu pisemnym
    int ile = 0, p = 0;
    while (a > 0 || b > 0) {
        p = (a % 10 + b % 10 + p) / 10;      // 1, gdy suma cyfr z przeniesieniem >= 10
        ile += p;
        a /= 10;
        b /= 10;
    }
    return ile;
}

#include <vector>
using namespace std;

bool czy_pierwsza(long long n) {
    if (n < 2) return false;
    for (long long d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}

vector<long long> czynniki(long long n) {
    vector<long long> wynik;
    for (long long d = 2; d * d <= n; d++)
        while (n % d == 0) {
            wynik.push_back(d);
            n /= d;
        }
    if (n > 1)             // została jedna duża liczba pierwsza
        wynik.push_back(n);
    return wynik;
}

#include <vector>
using namespace std;

vector<int> sito(int n) {
    vector<bool> pierwsza(n + 1, true);
    pierwsza[0] = pierwsza[1] = false;
    for (int i = 2; i * i <= n; i++)
        if (pierwsza[i])
            for (int j = i * i; j <= n; j += i)   // wielokrotności i
                pierwsza[j] = false;
    vector<int> wynik;
    for (int k = 2; k <= n; k++)
        if (pierwsza[k]) wynik.push_back(k);
    return wynik;
}

long long nwd_odejmowanie(long long a, long long b) {
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

long long nwd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long nwd_rek(long long a, long long b) {
    if (b == 0) return a;
    return nwd_rek(b, a % b);
}

long long nww(long long a, long long b) {
    return a / nwd(a, b) * b;    // najpierw dzielenie: chroni przed przepełnieniem
}

// zwraca d = NWD(a, b) i ustawia x, y tak, że d = a·x + b·y
long long nwd_rozszerzony(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long d = nwd_rozszerzony(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

#include <string>
using namespace std;

const string CYFRY = "0123456789ABCDEF";

string na_system(long long n, int p) {
    if (n == 0) return "0";
    string wynik = "";
    while (n > 0) {
        wynik = CYFRY[n % p] + wynik;   // reszty czytamy od końca
        n /= p;
    }
    return wynik;
}

long long z_systemu(const string& s, int p) {   // schemat Hornera
    long long wynik = 0;
    for (char znak : s)
        wynik = wynik * p + (long long)CYFRY.find(znak);
    return wynik;
}

#include <vector>
using namespace std;

// wsp: współczynniki od najwyższej potęgi, np. 2x³ - 3x² + x - 5 -> {2, -3, 1, -5}
long long horner(const vector<long long>& wsp, long long x) {
    long long w = 0;
    for (long long a : wsp)
        w = w * x + a;
    return w;
}

int bloki(long long n) {          // bloki takich samych cyfr w zapisie binarnym n > 0
    int ile = 1, ostatni = n % 2;
    n /= 2;
    while (n > 0) {
        if (n % 2 != ostatni) {   // zmiana cyfry: zaczyna się nowy blok
            ile++;
            ostatni = n % 2;
        }
        n /= 2;
    }
    return ile;
}

int jedynki(long long n) {        // liczba jedynek w zapisie binarnym
    int ile = 0;
    while (n > 0) {
        ile += n & 1;             // ostatni bit
        n >>= 1;                  // przesunięcie w prawo, czyli n / 2
    }
    return ile;
}

bool potega_dwojki(long long n) { // n > 0 ma dokładnie jedną jedynkę
    return (n & (n - 1)) == 0;    // nawiasy obowiązkowe: == wiąże mocniej niż &
}

long long gray(long long n) {     // kod Graya: sąsiednie liczby różnią się jednym bitem
    return n ^ (n >> 1);
}

long long potega(long long a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 1) return a * potega(a, n - 1);
    long long p = potega(a, n / 2);
    return p * p;                // jedno wywołanie, wynik użyty dwa razy
}

long long potega_mod(long long a, long long n, long long m) {
    long long wynik = 1;
    a %= m;
    while (n > 0) {
        if (n % 2 == 1)          // bieżący bit wykładnika to 1
            wynik = wynik * a % m;
        a = a * a % m;
        n /= 2;
    }
    return wynik;
}

long long silnia(int n) {
    if (n <= 1) return 1;        // warunek zakończenia
    return n * silnia(n - 1);
}

long long fib_rek(int n) {       // proste, ale wykładniczo wolne
    if (n < 2) return n;
    return fib_rek(n - 1) + fib_rek(n - 2);
}

long long fib(int n) {           // iteracyjnie: O(n)
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

#include <string>
#include <vector>
#include <utility>
using namespace std;

void ciagi(string s, int n, int k, vector<string>& wynik) {   // napisy długości n z cyfr 0..k-1
    if ((int)s.size() == n) {
        wynik.push_back(s);
        return;
    }
    for (int c = 0; c < k; c++)
        ciagi(s + to_string(c), n, k, wynik);
}

vector<vector<int>> podzbiory(const vector<int>& t) {   // każdy podzbiór to maska 0..2ⁿ-1
    int n = t.size();
    vector<vector<int>> wynik;
    for (int maska = 0; maska < (1 << n); maska++) {
        vector<int> p;
        for (int i = 0; i < n; i++)
            if (maska >> i & 1) p.push_back(t[i]);
        wynik.push_back(p);
    }
    return wynik;
}

void permutacje(vector<int>& t, int k, vector<vector<int>>& wynik) {
    if (k == (int)t.size()) wynik.push_back(t);
    for (int i = k; i < (int)t.size(); i++) {   // na pozycję k każdy pozostały element
        swap(t[k], t[i]);
        permutacje(t, k + 1, wynik);
        swap(t[k], t[i]);                       // cofamy zamianę
    }
}

#include <vector>
using namespace std;

int indeks(const vector<int>& t, int x) {
    for (int i = 0; i < (int)t.size(); i++)
        if (t[i] == x) return i;
    return -1;                   // nie ma takiego elementu
}

int minimum(const vector<int>& t) {
    int m = t[0];
    for (int x : t)
        if (x < m) m = x;
    return m;
}

int najdluzszy_rosnacy(const vector<int>& t) {
    // najdłuższy fragment kolejnych elementów, w którym każdy jest większy od poprzedniego
    int najl = 1, dl = 1;
    for (int i = 1; i < (int)t.size(); i++) {
        if (t[i] > t[i - 1]) dl++;
        else dl = 1;
        if (dl > najl) najl = dl;
    }
    return najl;
}

#include <vector>
#include <utility>
using namespace std;

pair<int, int> min_max(const vector<int>& t) {
    int n = t.size(), mn, mx, i;
    if (n % 2 == 1) {
        mn = mx = t[0];
        i = 1;
    } else {
        if (t[0] < t[1]) { mn = t[0]; mx = t[1]; }
        else { mn = t[1]; mx = t[0]; }
        i = 2;
    }
    for (; i < n; i += 2) {
        int a = t[i], b = t[i + 1];
        if (a > b) swap(a, b);   // 1 porównanie w parze
        if (a < mn) mn = a;      // mniejszy z pary walczy tylko o minimum
        if (b > mx) mx = b;      // większy tylko o maksimum
    }
    return {mn, mx};
}

#include <vector>
#include <algorithm>
using namespace std;

vector<long long> sumy_prefiksowe(const vector<int>& t) {
    vector<long long> P(t.size() + 1, 0);       // P[i] = t[0] + ... + t[i-1]
    for (int i = 0; i < (int)t.size(); i++)
        P[i + 1] = P[i] + t[i];
    return P;
}
// suma fragmentu t[a..b] (włącznie) to P[b + 1] - P[a]

// fragment o co najmniej k elementach z największą średnią; ustawia start i dl
double najlepsza_srednia(const vector<int>& t, int k, int& start, int& dl) {
    vector<long long> P = sumy_prefiksowe(t);
    int n = t.size();
    long long suma = P[k];
    start = 0;
    dl = k;
    for (int a = 0; a < n; a++)
        for (int b = a + k; b <= n; b++) {      // fragment t[a..b-1]
            long long s = P[b] - P[a];
            if (s * dl > suma * (b - a)) {      // s/(b-a) > suma/dl bez dzielenia
                suma = s;
                start = a;
                dl = b - a;
            }
        }
    return (double)suma / dl;
}

long long najwieksza_suma(const vector<int>& t) {   // algorytm Kadane, O(n)
    long long naj = t[0], biezaca = t[0];
    for (int i = 1; i < (int)t.size(); i++) {
        biezaca = max((long long)t[i], biezaca + t[i]);   // przedłużamy albo od nowa
        naj = max(naj, biezaca);
    }
    return naj;
}

#include <vector>
using namespace std;

int szukaj_binarnie(const vector<int>& t, int x) {   // t musi być posortowana rosnąco
    int lewy = 0, prawy = (int)t.size() - 1;
    while (lewy <= prawy) {
        int srodek = (lewy + prawy) / 2;
        if (t[srodek] == x) return srodek;
        if (t[srodek] < x) lewy = srodek + 1;   // x może być tylko na prawo
        else prawy = srodek - 1;                // x może być tylko na lewo
    }
    return -1;
}

int pierwszy_niemniejszy(const vector<int>& t, int x) {
    // indeks pierwszego elementu >= x; t.size(), gdy takiego nie ma
    int lewy = 0, prawy = t.size();
    while (lewy < prawy) {
        int s = (lewy + prawy) / 2;
        if (t[s] < x) lewy = s + 1;
        else prawy = s;
    }
    return lewy;
}

long long pierwiastek3(long long n) {   // najmniejsze p >= 1, dla którego p³ >= n
    long long lewy = 1, prawy = n;
    while (lewy < prawy) {
        long long s = (lewy + prawy) / 2;
        if (s * s * s < n) lewy = s + 1;  // s za małe
        else prawy = s;                   // s może być wynikiem
    }
    return lewy;
}

#include <vector>
#include <utility>
using namespace std;

void babelkowe(vector<int>& t) {
    int n = t.size();
    for (int i = 0; i < n - 1; i++) {
        bool zamiana = false;
        for (int j = 0; j < n - 1 - i; j++)   // ostatnie i elementów już stoi na miejscu
            if (t[j] > t[j + 1]) {
                swap(t[j], t[j + 1]);
                zamiana = true;
            }
        if (!zamiana) break;                  // przebieg bez zamian: koniec
    }
}

void przez_wybor(vector<int>& t) {
    int n = t.size();
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++)       // szukamy minimum w części nieposortowanej
            if (t[j] < t[m]) m = j;
        swap(t[i], t[m]);
    }
}

void przez_wstawianie(vector<int>& t) {
    for (int i = 1; i < (int)t.size(); i++) {
        int x = t[i], j = i - 1;
        while (j >= 0 && t[j] > x) {          // przesuwamy większe w prawo
            t[j + 1] = t[j];
            j--;
        }
        t[j + 1] = x;
    }
}

#include <vector>
using namespace std;

// sortuje t[lewy..prawy] włącznie
void sortuj_scalanie(vector<int>& t, int lewy, int prawy) {
    if (lewy >= prawy) return;
    int s = (lewy + prawy) / 2;
    sortuj_scalanie(t, lewy, s);
    sortuj_scalanie(t, s + 1, prawy);

    vector<int> pom;             // scalanie dwóch posortowanych połówek
    int i = lewy, j = s + 1;
    while (i <= s && j <= prawy) {
        if (t[i] <= t[j]) pom.push_back(t[i++]);
        else pom.push_back(t[j++]);
    }
    while (i <= s) pom.push_back(t[i++]);
    while (j <= prawy) pom.push_back(t[j++]);
    for (int k = 0; k < (int)pom.size(); k++)
        t[lewy + k] = pom[k];
}

#include <vector>
#include <utility>
using namespace std;

void quicksort(vector<int>& t, int lewy, int prawy) {
    if (lewy >= prawy) return;
    int pivot = t[prawy];        // element dzielący: ostatni
    int i = lewy;
    for (int j = lewy; j < prawy; j++)
        if (t[j] < pivot)        // mniejsze od pivota idą na początek
            swap(t[i++], t[j]);
    swap(t[i], t[prawy]);        // pivot na swoje ostateczne miejsce
    quicksort(t, lewy, i - 1);
    quicksort(t, i + 1, prawy);
}

// wywołanie: quicksort(t, 0, t.size() - 1);

#include <vector>
#include <algorithm>
using namespace std;

vector<int> przez_zliczanie(const vector<int>& t, int maks) {   // liczby 0..maks
    vector<int> ile(maks + 1, 0);
    for (int x : t) ile[x]++;
    vector<int> wynik;
    for (int v = 0; v <= maks; v++)
        for (int k = 0; k < ile[v]; k++)
            wynik.push_back(v);
    return wynik;
}

vector<double> kubelkowe(const vector<double>& t, int k = 10) {  // liczby z [0, 1)
    vector<vector<double>> kubelki(k);
    for (double x : t) kubelki[(int)(x * k)].push_back(x);
    vector<double> wynik;
    for (auto& kub : kubelki) {
        sort(kub.begin(), kub.end());   // kubełki są małe
        for (double x : kub) wynik.push_back(x);
    }
    return wynik;
}

#include <string>
#include <vector>
using namespace std;

bool palindrom(const string& s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

bool anagramy(const string& a, const string& b) {   // małe litery a-z
    if (a.size() != b.size()) return false;
    int ile[26] = {0};
    for (char z : a) ile[z - 'a']++;
    for (char z : b) ile[z - 'a']--;
    for (int x : ile)
        if (x != 0) return false;
    return true;
}

vector<int> wystapienia(const string& tekst, const string& wzorzec) {  // naiwnie
    vector<int> wynik;
    int n = tekst.size(), m = wzorzec.size();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && tekst[i + j] == wzorzec[j]) j++;
        if (j == m) wynik.push_back(i);
    }
    return wynik;
}

#include <string>
#include <utility>
using namespace std;

string cezar(const string& tekst, int k) {   // wielkie litery A-Z, reszta bez zmian
    string wynik = tekst;
    k = (k % 26 + 26) % 26;      // w C++ reszta z liczby ujemnej jest ujemna
    for (char& z : wynik)
        if (z >= 'A' && z <= 'Z')
            z = (z - 'A' + k) % 26 + 'A';
    return wynik;
}
// odszyfrowanie: cezar(szyfrogram, -k)

string vigenere(const string& tekst, const string& klucz, int kierunek = 1) {
    string wynik = tekst;
    for (int i = 0; i < (int)tekst.size(); i++) {
        int k = klucz[i % klucz.size()] - 'A';
        wynik[i] = ((tekst[i] - 'A' + kierunek * k) % 26 + 26) % 26 + 'A';
    }
    return wynik;
}

string przestaw_pary(string t) { // szyfr przestawieniowy: zamiana sąsiednich znaków
    for (int i = 0; i + 1 < (int)t.size(); i += 2)
        swap(t[i], t[i + 1]);
    return t;
}

#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

vector<pair<int, int>> kwadraty(const vector<string>& T) {   // środki kwadratów 3×3
    vector<pair<int, int>> wynik;
    for (int i = 1; i + 1 < (int)T.size(); i++)
        for (int j = 1; j + 1 < (int)T[0].size(); j++) {
            bool dobry = true;
            for (int di = -1; di <= 1; di++)
                for (int dj = -1; dj <= 1; dj++)
                    if (T[i + di][j + dj] != T[i][j]) dobry = false;
            if (dobry) wynik.push_back({i, j});
        }
    return wynik;
}

bool dojscie(const vector<vector<int>>& A) {   // w prawo lub w dół, tylko po polach 1
    int n = A.size(), m = A[0].size();
    vector<vector<bool>> P(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (A[i][j] == 1) {
                if (i == 0 && j == 0) P[i][j] = true;
                else P[i][j] = (i > 0 && P[i - 1][j]) || (j > 0 && P[i][j - 1]);
            }
    return P[n - 1][m - 1];
}

int obszar(const vector<string>& T, int i, int j) {   // BFS: wielkość obszaru wokół (i, j)
    int n = T.size(), m = T[0].size(), ile = 1;
    vector<vector<bool>> odw(n, vector<bool>(m, false));
    queue<pair<int, int>> kolejka;
    odw[i][j] = true;
    kolejka.push({i, j});
    int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};
    while (!kolejka.empty()) {
        auto [y, x] = kolejka.front();
        kolejka.pop();
        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k], nx = x + dx[k];
            if (ny >= 0 && ny < n && nx >= 0 && nx < m && !odw[ny][nx] && T[ny][nx] == T[i][j]) {
                odw[ny][nx] = true;
                ile++;
                kolejka.push({ny, nx});
            }
        }
    }
    return ile;
}

#include <vector>
#include <utility>
using namespace std;

const int PUSTE = -1;   // drzewo w tablicy: korzeń D[1], dzieci węzła i to 2i i 2i+1

void wstaw_bst(vector<int>& D, int x) {
    int i = 1;
    while (i < (int)D.size() && D[i] != PUSTE)
        i = x < D[i] ? 2 * i : 2 * i + 1;   // mniejsze w lewo, większe w prawo
    if ((int)D.size() <= i) D.resize(i + 1, PUSTE);
    D[i] = x;
}

void inorder(const vector<int>& D, int i, vector<int>& wynik) {   // daje liczby rosnąco
    if (i >= (int)D.size() || D[i] == PUSTE) return;
    inorder(D, 2 * i, wynik);
    wynik.push_back(D[i]);
    inorder(D, 2 * i + 1, wynik);
}

void wstaw_kopiec(vector<int>& T, int x) {   // kopiec w T[1..n]: rodzic s to s / 2
    T.push_back(x);
    int s = T.size() - 1;
    while (s > 1 && T[s] > T[s / 2]) {       // większy od rodzica wędruje w górę
        swap(T[s], T[s / 2]);
        s /= 2;
    }
}

// szef[x] < x to bezpośredni przełożony x; szef[1] = 0
void hierarchia(const vector<int>& szef, vector<int>& dzieci, vector<int>& wszyscy, vector<int>& glebokosc) {
    int n = szef.size() - 1;
    dzieci.assign(n + 1, 0);
    wszyscy.assign(n + 1, 0);
    glebokosc.assign(n + 1, 0);
    for (int x = 2; x <= n; x++) {
        dzieci[szef[x]]++;
        glebokosc[x] = glebokosc[szef[x]] + 1;   // szef ma mniejszy numer: już policzony
    }
    for (int x = n; x >= 2; x--)                 // od końca: podwładni x są już zliczeni
        wszyscy[szef[x]] += wszyscy[x] + 1;
}

#include <cmath>
using namespace std;

double f(double x) {
    return x * x * x - x - 2;
}

double bisekcja(double a, double b, double eps) {   // f(a) i f(b) mają różne znaki
    while (b - a > eps) {
        double s = (a + b) / 2;
        if (f(a) * f(s) <= 0) b = s;   // zmiana znaku w lewej połowie
        else a = s;
    }
    return (a + b) / 2;
}

double pierwiastek(double p, double eps) {   // metoda Herona (Newtona) dla p > 0
    double x = p;
    while (fabs(x * x - p) > eps)
        x = (x + p / x) / 2;
    return x;
}

double g(double x) {
    return x * x;
}

double pole_prostokaty(double a, double b, int n) {   // wysokość w środku paska
    double h = (b - a) / n, s = 0;
    for (int i = 0; i < n; i++)
        s += g(a + i * h + h / 2);
    return s * h;
}

double pole_trapezy(double a, double b, int n) {
    double h = (b - a) / n, s = (g(a) + g(b)) / 2;
    for (int i = 1; i < n; i++)
        s += g(a + i * h);
    return s * h;
}

#include <random>
using namespace std;

double pi_monte_carlo(int n) {
    mt19937 gen(2026);                            // generator z ustalonym ziarnem
    uniform_real_distribution<double> los(0.0, 1.0);
    int trafione = 0;
    for (int i = 0; i < n; i++) {
        double x = los(gen), y = los(gen);        // punkt w kwadracie 1×1
        if (x * x + y * y <= 1) trafione++;       // wewnątrz ćwiartki koła
    }
    return 4.0 * trafione / n;
}

#include <cstdlib>
#include <vector>
#include <utility>
using namespace std;

long long iloczyn(long long ax, long long ay, long long bx, long long by, long long cx, long long cy) {
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);   // iloczyn wektorowy AB × AC
}
// > 0: C na lewo od prostej AB, < 0: na prawo, = 0: A, B, C leżą na jednej prostej

double pole_trojkata(long long ax, long long ay, long long bx, long long by, long long cx, long long cy) {
    return llabs(iloczyn(ax, ay, bx, by, cx, cy)) / 2.0;
}

bool mniejszy_ulamek(long long a, long long b, long long c, long long d) {   // a/b < c/d, b, d > 0
    return a * d < c * b;                // bez dzielenia: wynik dokładny
}

vector<pair<long long, long long>> pozycje(const vector<pair<long long, long long>>& ruchy) {
    long long x = 0, y = 0;
    vector<pair<long long, long long>> wynik;
    for (auto [dx, dy] : ruchy) {
        x += dx;
        y += dy;
        wynik.push_back({x, y});
    }
    return wynik;
}

#include <vector>
using namespace std;

int reszta_zachlanna(int kwota, const vector<int>& nominaly) {   // od największego
    int ile = 0;
    for (int m : nominaly) {
        ile += kwota / m;
        kwota %= m;
    }
    return ile;
}

int reszta_optymalna(int kwota, const vector<int>& nominaly) {
    vector<int> dp(kwota + 1, kwota + 1);   // dp[k]: najmniej monet na kwotę k
    dp[0] = 0;
    for (int k = 1; k <= kwota; k++)
        for (int m : nominaly)
            if (m <= k && dp[k - m] + 1 < dp[k])
                dp[k] = dp[k - m] + 1;
    return dp[kwota];
}

#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int najwiecej_przedzialow(vector<pair<int, int>> P) {   // pary (początek, koniec)
    sort(P.begin(), P.end(), [](auto a, auto b) { return a.second < b.second; });
    int ile = 0;
    bool pierwszy = true;
    int koniec = 0;
    for (auto [p, k] : P)                // od najwcześniejszego końca
        if (pierwszy || p >= koniec) {
            ile++;
            koniec = k;
            pierwszy = false;
        }
    return ile;
}

#include <vector>
#include <algorithm>
using namespace std;

// opady w mm, dzień po dniu; ustawia pierwszy_pelny (0, gdy zbiornik nigdy nie był pełny)
int symuluj(const vector<int>& opady, int pojemnosc, int& pierwszy_pelny, int start = 100) {
    int stan = start, braki = 0;              // litry w zbiorniku
    pierwszy_pelny = 0;
    for (int d = 0; d < (int)opady.size(); d++) {
        stan = min(pojemnosc, stan + 10 * opady[d]);   // deszcz; nadmiar się przelewa
        if (stan == pojemnosc && pierwszy_pelny == 0)
            pierwszy_pelny = d + 1;
        if (stan >= 30) stan -= 30;           // podlewanie
        else braki++;                         // za mało wody tego dnia
    }
    return braki;
}

int najmniejsza_pojemnosc(const vector<int>& opady) {   // pierwsza bez braków wody
    int p;
    for (int pojemnosc = 100; pojemnosc <= 10000; pojemnosc += 10)
        if (symuluj(opady, pojemnosc, p) == 0) return pojemnosc;
    return -1;
}