// T1
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回满足条件的最大的x。
     * @param a int整型 代表题意中的a
     * @param b int整型 代表题意中的b
     * @param n int整型 代表题意中的n
     * @return int整型
     */
    int solve(int a, int b, int n) {
        // write code here
        int mod = n%a;
        if(mod >= b)
            return n/a*a+b;
        return n/a*a-a+b;
    }
};

//T2

class Solution {
public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int string2(int k, string s) {
        // write code here
        typedef pair<int,int> pii;
        vector<int> count(26, 0);
        for(auto c : s)
            count[c-'a']++; //计数
        int maxlen = 0;
        for(int i = 0; i < 26; ++i)
        {
            vector<pii> cost(26);
            for(int j = 0; j < 26; ++j)
                cost[j] = {abs(i-j), j};//cost花费, idx
            int num = k, len = 0;
            sort(cost.begin(), cost.end());//花费小的优先
            for(int j = 0; j < 26 && num > 0; ++j)
            {
                int ct = cost[j].first;//花费
                int id = cost[j].second;//字符id
                if(count[id] == 0)//字符没有的
                    continue;
                if(ct == 0)//花费为0的
                {
                    len += count[id];
                    continue;
                }
                int add = min(num/ct, count[id]);//可以拿的字符个数
                len += add;
                num -= add*ct;
            }
            maxlen = max(maxlen, len);
        }
        return maxlen;
    }
};

	

// T3
class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    typedef long long ll;
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        if(m == 0) return 1;
        int mod = 1e9+7;
        vector<vector<ll>> dp(n, vector<ll>(m+1, 0));
        for(int i = 0; i < n; i++)
            dp[i][1] = 1;
        for(int t = 2; t <= m; t++)
        {
            for(int i = 0; i < n; ++i)
            {
                if(dp[i][t-1] == 0)
                    continue;
                for(int j = i+k+1; j < n; ++j)
                {
                    dp[j][t] += dp[i][t-1];
                    dp[j][t] = (dp[j][t]%mod);
                }
            }
        }
        ll ans = 0;
        for(int i = 0; i < n; ++i)
            ans = (ans+dp[i][m])%mod;
        return ans;
    }
};