DP

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
const int mod = 1e9 + 7; // 998244353
/*
int f[25];
int memo[50];

int fibo(int n){
    if(n <= 1) // 0 1
        return 1;
    if(memo[n] != 0)
        return memo[n];
    return memo[n] = fibo(n - 1) + fibo(n - 2);
}
*/
/*
const int N = 1e5 + 5;
int dp[N];
*/

int dp[1005][1005];

signed main()
{
    fastio;
    // fibo: 1 1 2 3 5 8 13 21 34 55 ...
/*
// A
    int n;
    cin >> n;


    f[0] = 1;
    for(int i = 1; i <= n; i++)
        f[i] = f[i - 1] * i;
    */
    /*
    // B
    int n;
    cin >> n;
    f[0] = 1; // 2 in C
    f[1] = 1;
    for(int i = 2; i <= n; i++){
        f[i] = f[i - 1] + f[i - 2];
    }

    cout << f[n];
    */


    // dp[i] --> 1 to i number of ways
    /*
    //D
    int n , k;
    cin >> n >> k;
    dp[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(i <= j)  break;
            dp[i] += dp[i - j];
        }
    }
    cout << dp[n];
    */

    /*
    3
    1 -1 1
    2

    0 1 -1 1 0
    */
    /*
    // E
    // dp[i] --> 0 to i max sum


    int n , k;
    cin >> n;
    int a[n + 5];
    a[n + 1] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> k;

    dp[0] = 0;
    for(int i = 1; i <= n + 1; i++){
        dp[i] = LLONG_MIN;
        for(int j = 1; j <= k; j++){
            if(i < j)   break;
            dp[i] = max(dp[i] , dp[i - j] + a[i]);
        }
    }
    cout << dp[n + 1];
    */
    /*
    // F
    // dp[i] --> 1 to i min cost (sum of abs difference)
    int n;
    cin >> n;
    int a[n + 5];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    dp[1] = 0;
    dp[2] = abs(a[2] - a[1]);
    for(int i = 3; i <= n; i++){
        // from i - 1 or i - 2
        dp[i] = LLONG_MAX;
        dp[i] = min({dp[i] , dp[i - 1] + abs(a[i] - a[i - 1]) , dp[i - 2] + abs(a[i] - a[i - 2])});
    }
    cout << dp[n];
    */
    /*
    // G
    int n , k;
    cin >> n >> k;
    int a[n + 5];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    dp[1] = 0;
    for(int i = 2; i <= n; i++){
        dp[i] = LLONG_MAX;
        for(int j = 1; j <= k; j++){
            if(i - j < 1)   continue;
            dp[i] = min(dp[i] , dp[i - j] + abs(a[i] - a[i - j]));
        }
    }
    cout << dp[n];
    */
    /*
    1 1 1 1
    1 2 3 4
    1 3 6 10
    1 4 10 20
    */
    /*
    // H
    int n , m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1) // Starting Point
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m];
    */
    /*
    // I
    int n;
    cin >> n;
    char a[n + 5][n + 5];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }


    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j] == '*'){
                dp[i][j] = 0; // gede bilmiremki
                continue;
            }
            if(i == 1 && j == 1)
                dp[i][j] = 1;
            else
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
        }
    }
    cout << dp[n][n];
    */
    /*
    // J
    int n , m;
    cin >> n >> m;
    int a[n + 5][m + 5];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1){
                dp[i][j] = a[i][j];
                continue;
            }
            dp[i][j] = LLONG_MAX;
            if(i > 1)
                dp[i][j] = min(dp[i][j] , dp[i - 1][j] + a[i][j]);
            if(j > 1)
                dp[i][j] = min(dp[i][j] , dp[i][j - 1] + a[i][j]);
        }
    }
    cout << dp[n][m];
    */
}