\begin{tutorial}{Серебряный статус в авиакомпании}

При данных ограничениях задачу проще всего решать перебором вариантов. А именно, переберём, сколько пакетов по $30\,000$ будем менять на $5\,000$ квалификационных, а из оставшихся средств~--- сколько пакетов по $7\,500$ миль будем менять на $1\,000$ каждый. Из этих вариантов выберем тот, при котором количество квалификационных миль будет не менее $20\,000$, а общее число миль будет как можно больше.

Код программы на языке Python:

\lstset{
    basicstyle=\linespread{0.9}\ttfamily,
    escapeinside={(*}{*)}
}

\begin{lstlisting}[language=Python, frame=single]
n = int(input())
k = int(input())
mx = 0
for i in range(n // 30000 + 1):
    for j in range((n - i * 30000) // 7500 + 1):
        nn = n - i * 30000 - j * 7500
        kk = k
        if nn < k:
            kk = nn # (* квалификационные мили были потрачены на обмен *)
        kk += i * 5000 + j * 1000 # (* новое число квалификационных миль *)
        nn += i * 5000 + j * 1000 # (* новое число миль *)
        if kk >= 20000: # (* квалификационных миль хватает для статуса *) 
            if nn > mx:
                mx = nn
if mx > 0:
    print(mx)
else:
    print(-1)
\end{lstlisting}

Но задачу можно решить и разбором случаев. Определим, сколько пакетов по $1\,000$ квалификационных миль нам не хватает до достижения $20\,000$ миль. Разделим это количество на пять и обменяем как минимум такое количество пакетов по $5\,000$ миль, остаток обменяем по $1\,000$ миль. Но если осталось четыре пакета по $1\,000$, то вместо них выгоднее обменять дополнительный пакет в $5\,000$ миль, потому что при той же стоимости мы получим в итоге на $1\,000$ миль больше. При этих необходимых операциях на обмены могут расходоваться и имевшиеся квалификационные мили, что может привести к невозможности получения серебряного статуса, даже когда общего количества миль на обмены хватает.

\begin{lstlisting}[language=Python, frame=single]
n = int(input())
k = int(input())
# (* используем округление вверх до 1000 при подсчете недостающих пакетов *)
l = (max(0, 20000 - k) + 999) // 1000 
if l % 5 == 4:
    # (* выгоднее обменять лишний пакет в 5000 миль вместо четырех по 1000 миль *)
    l5 = (l + 1) // 5
    # (* квалификационные мили с учетом возможного их уменьшения при обмене *)
    k = min(k, n - 30000 * l5) + 5000 * l5 
    n -= 25000 * l5 # (* оставшиеся мили *)
else:
    l1 = l % 5
    l5 = l // 5
    k = min(k, n - 30000 * l5 - 7500 * l1) + 5000 * l5 + 1000 * l1
    n -= (25000 * l5 + 6500 * l1) # (* оставшиеся мили *)
if k >= 20000: # (* квалификационных миль достаточно *)
    print(n)
else:
    print(-1)
\end{lstlisting}




\end{tutorial}
