# ACSI NOI Workshop 2021 Solution

## Lesson Problems

### Problem 1: Quality-Adjusted Life-Year

- https://open.kattis.com/problems/qaly

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

// Declare variables here
int N;
float q, y, answer;

int main() {
    // Read integer N
    cin >> N;

    // Repeat N times:
    for (int i = 0; i < N; i++) {
        //  1. Read float q, y
        cin >> q >> y;
        //  2. Add q * y to answer
        answer += q * y;
    }

    // Output answer
    cout << answer;
}

### Problem 2: Poker Hand

- https://open.kattis.com/problems/pokerhand

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

int ans;
string S[5];
// Declare variables here
unordered_map<char, int> freq;

int main() {
    // Read 5 strings into array S[]
    for (int i = 0; i < 5; i++) {
        cin >> S[i];
    }

    // For each hand in S[]:
    for (int i = 0; i < 5; i++) {
        // 1. Get the rank
        char rank = S[i][0];
        // 2. Increase the rank's count by 1
        freq[rank]++;
    }

    // For each rank's count:
    for (auto x : freq) {
        // 1. Update answer if count > current answer
        ans = max(ans, x.second);
    }

    // Output answer
    cout << ans;
}

### Problem 3: Bungee Builder

- https://open.kattis.com/problems/bungeebuilder

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

#define MAXN 1000006

// Declare variables here
int N, height[MAXN];

// Sliding window from left to right, returns the max distance, O(N)
int sliding(int N, int height[]) {
    int i = 0, ans = 0, bottom = height[0];

    for (int j = 1; j < N; j++) {
        if (height[i] <= height[j]) {
            // Form a bridge between i and j, calculate the max distance
            ans = max(ans, height[i] - bottom);
            // Set j as the new i
            i = j;
            bottom = height[i];
        } else {
            // Keep searching for the lowest bottom
            bottom = min(bottom, height[j]);
        }
    }

    return ans;
}

int main() {
    // Read inputs
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> height[i];
    }

    // Get forward result
    int ans_forward = sliding(N, height);
    // Reverse the height array in-place
    reverse(begin(height), begin(height) + N);
    // Get backward result
    int ans_backward = sliding(N, height);

    // Output the max of both forward & backward result
    cout << max(ans_forward, ans_backward);
}

### Problem 4: The Monkey and the Oiled Bamboo

- https://onlinejudge.org/external/120/12032.pdf

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

// Bad practice in software engineering, but ok for CP
#define MAXN 100005
#define MAXR 10000007

// Declare variables here
int T, N, R[MAXN], ans;

// Returns true if can reach the top rung with k
bool can_reach(int k, int R[]) {
    for (int i = 0; i < N; i++) {
        int gap = (i == 0) ? R[0] : R[i] - R[i - 1];

        if (gap > k) {
            return false;
        } else if (gap == k) {
            k--;
        }
    }
    return true;
}

int main() {
    // Read T
    cin >> T;
    // For each case i
    for (int i = 0; i < T; i++) {
        // Read input
        cin >> N;
        for (int j = 0; j < N; j++) {
            cin >> R[j];
        }

        // Initialize binary search low & high
        int lo = 1, hi = MAXR;
        // Binary search terminating condition
        while (lo <= hi) {
            // Pick the middle as k
            int mid = hi - (hi - lo) / 2;  // Prevent integer overflow

            if (can_reach(mid, R)) {
                // Keep the answer
                ans = mid;
                // Look for smaller k
                hi = mid - 1;
            } else {
                // Look for bigger k
                lo = mid + 1;
            }
        }

        // Output answer
        printf("Case %d: %d\n", i + 1, ans);
    }
}

### Problem 5: Station Balance

- https://onlinejudge.org/external/4/410.pdf

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

#define MAXS 10

// Declare variables here
int C, S, M[MAXS], TC = 1, s1, s2;
double imb, sum, avg;

int main() {
    while (cin >> C >> S) {
        sum = imb = 0;
        // Read input
        for (int i = 0; i < S; i++) {
            cin >> M[i];
            sum += M[i];
        }
        avg = sum / C;

        // Pad M with 0
        for (int i = S; i < 2 * C; i++) {
            M[i] = 0;
        }

        sort(M, M + 2 * C);

        // Output answer
        printf("Set #%d\n", TC++);
        for (int i = 0; i < C; i++) {
            printf(" %d:", i);
            s1 = M[i], s2 = M[2 * C - i - 1];
            // Don't print 0
            if (s1) printf(" %d", s1);
            if (s2) printf(" %d", s2);
            printf("\n");
            imb += abs(avg - (s1 + s2));
        }

        // 5 digits after decimal point
        printf("IMBALANCE = %.5f\n\n", imb);
    }
}

### Problem 6: Wedding Shopping

- https://onlinejudge.org/external/114/11450.pdf

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

#define INF 1000000009
#define MAXC 20
#define MAXK 20
#define MAXM 200

int N, M, C, K, price[MAXC][MAXK], memo[MAXK][MAXM];

// g is garment type, b is current budget
int buy(int g, int b) {
    if (b < 0) return -INF;
    if (g == C) return M - b;
    if (memo[g][b] != -1) return memo[g][b];

    // Try each model k for garment g
    int ans = -1;
    for (int k = 1; k <= price[g][0]; k++)
        ans = max(ans, buy(g + 1, b - price[g][k]));
    return memo[g][b] = ans;
}

int main() {
    scanf("%d", &N);
    while (N--) {
        // Read input
        scanf("%d %d", &M, &C);
        for (int i = 0; i < C; i++) {
            // price[i][0] is number of models for garment i
            scanf("%d", &price[i][0]);
            for (int j = 1; j <= price[i][0]; j++)
                // price[i][j] is the price of model j for garment i
                scanf("%d", &price[i][j]);
        }

        // Clear memory
        memset(memo, -1, sizeof memo);

        int ans = buy(0, M);

        // Output answer
        if (ans >= 0)
            printf("%d\n", ans);
        else
            printf("no solution\n");
    }
}

## Day 1 Homework

### Delimiter Soup

- https://open.kattis.com/problems/delimitersoup

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

int L;
string str;
stack<char> expect;
unordered_map<char, char> match = {{'(', ')'}, {'[', ']'}, {'{', '}'}};

int main() {
    // Read input, cin >> ws to consume endline token for getline to work
    cin >> L >> ws;
    getline(cin, str);

    for (int i = 0; i < L; i++) {
        char c = str[i];
        // Ignore whitespace
        if (isspace(c)) continue;

        auto delim = match.find(c);
        if (delim != match.end()) {
            // c is open delimiter
            expect.push(delim->second);  // Store the expected close delimiter in a stack
        } else {
            // c is close delimiter
            if (!expect.empty() && c == expect.top())
                expect.pop();
            else {
                // c is not the expected close delimiter
                cout << c << " " << i;
                // Terminate program early
                return 0;
            }
        }
    }
    cout << "ok so far";
}

### Teque

- https://open.kattis.com/problems/teque

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

int N, x;
string op;
deque<int> d1, d2;
vector<int> ans;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> op >> x;

        // O(1) time for every operation type
        if (op == "get")
            ans.push_back(x < d1.size() ? d1[x] : d2[x - d1.size()]);
        else if (op == "push_back")
            d2.push_back(x);
        else if (op == "push_front")
            d1.push_front(x);
        else if (op == "push_middle")
            // Insert at the front of d2
            d2.push_front(x);

        // Rebalance d1 and d2
        // d1 is always the same size or 1 item more than d2
        if (d1.size() < d2.size()) {
            d1.push_back(d2.front());
            d2.pop_front();
        } else if (d1.size() > d2.size() + 1) {
            d2.push_front(d1.back());
            d1.pop_back();
        }
    }

    // Output all answer at one go for speed
    for (int x : ans)
        cout << x << "\n";
}

### Pivot

- https://open.kattis.com/problems/pivot

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

#define MAXN 100005

int N, a[MAXN], max_left[MAXN], min_right[MAXN];

int main() {
	// Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> a[i];

    // min_left[i] is the minimum value from everything to the left of a[i]
    max_left[0] = a[0];
    for (int i = 1; i < N; i++)
        max_left[i] = max(max_left[i - 1], a[i]);

    // max_right[i] is the maximum value from everything to the left of a[i]
    min_right[N - 1] = a[N - 1];
    for (int i = N - 2; i >= 0; i--)
        min_right[i] = min(min_right[i + 1], a[i]);

    int ans = 0;
    for (int i = 0; i < N; i++)
        // Count number of max_left[i] == min_right[i]
        ans += (max_left[i] == min_right[i]);

    // Output answer
    cout << ans;
}

### Disastrous Downtime

- https://open.kattis.com/problems/downtime

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

#define MAXN 100005

int n, k, request, ans, t[MAXN];
queue<int> process;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
        // Add time for request to finish processed
        process.push(t[i] + 1000);
        // Add request count by 1
        request++;

        // Remove all processed requests before t[i]
        while (!process.empty() && process.front() <= t[i]) {
            process.pop();
            request--;
        }

        // Update answer
        ans = max(ans, request);
    }

    // Note the float conversion for ceil to work
    cout << ceil((float)ans / k) << "\n";
}

## Day 2 Homework

### Knigs of the Forest

- https://open.kattis.com/problems/knigsoftheforest

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

#define MAXN 100005

int k, n, y, p, karl, winner, power[MAXN];
priority_queue<int> pool;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input
    cin >> k >> n;
    for (int i = 0; i <= n + k - 2; i++) {
        cin >> y >> p;
        // Store Karl's power
        if (i == 0) karl = p;
        // If year is 2011, it is an initial moose
        if (y == 2011) pool.push(p);
        // Otherwise, it is a replacement moose
        else power[y - 2011] = p;
    }

    // Simulate from index 0 to index n - 1
    for (int i = 0; i < n; i++) {
        winner = pool.top();
        // Karl wins, early terminate
        if (winner == karl) {
            cout << i + 2011 << "\n";
            return 0;
        } else {
            // Remove winner
            pool.pop();
            // Insert next year's replacement
            pool.push(power[i + 1]);
        }
    }
    // Karl never wins, output unknown
    cout << "unknown\n";
}

### Candy Division

- https://open.kattis.com/problems/candydivision

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

// Using 'll' as the shorthand of 'long long'
typedef long long ll;

// Note that we need to use long long instead of integers due to constraints (10^12)
ll n, sqrt_n;
// Using set because it automatically sorts items and removes duplicates
set<ll> ans;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input
    cin >> n;

    sqrt_n = sqrt(n);
    // Find divisors from 1 to square root of n
    for (ll i = 1; i <= sqrt_n; i++) {
        // If n mod i = 0, i.e. n is divisible by i
        if (n % i == 0) {
            // Problem requires (divisors - 1)
            ans.insert(i - 1);
            ans.insert((n / i) - 1);
        }
    }

    // Output answer
    for (auto it = ans.begin(); it != ans.end(); it++)
        cout << *it << " ";
    cout << "\n";
}

### Doctor Kattis

- https://open.kattis.com/problems/doctorkattis

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

// A Cat is a pair of <level, time>
typedef pair<int, int> Cat;

#define fi first
#define se second

int n, op, level, inc;
string name;

struct CatComparator {
    bool operator()(const Cat& cat1, const Cat& cat2) const {
        // Sort Cats by level descending, then by time ascending
        return cat1.fi != cat2.fi ? cat1.fi > cat2.fi : cat1.se < cat2.se;
    }
};

map<Cat, string, CatComparator> cat_to_name;  // Cat -> name
unordered_map<string, Cat> name_to_cat;       // name -> Cat

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input
    cin >> n;
    for (int time = 0; time < n; time++) {
        cin >> op;
        if (op == 0) {
            // Arrive at clinic
            cin >> name >> level;

            // Create a new entry in both containers
            Cat cat = {level, time};  // O(1)
            cat_to_name[cat] = name;  // O(logn)
            name_to_cat[name] = cat;  // O(1)
        } else if (op == 1) {
            // Update infection level
            cin >> name >> inc;

            // Use unordered_map to retrieve Cat by name
            Cat& cat = name_to_cat[name];  // O(1)
            // Remove the Cat entry from map
            cat_to_name.erase(cat);  // O(logn)
            // Increment infection level
            // At line 45, Cat is a reference to name_to_cat's value,
            // thus name_to_cat's value is updated by line 51
            cat.fi += inc;
            // Insert the updated cat into map
            // We have to delete the old Cat->name entry from cat_to_name and
            // insert a new one because Cat is a key in cat_to_name, not a value.
            cat_to_name[cat] = name;  // O(logn)
        } else if (op == 2) {
            // Leave clinic
            cin >> name;

            Cat& cat = name_to_cat[name];  // O(1)
            // Remove Cat entry from both containers
            cat_to_name.erase(cat);   // O(logn)
            name_to_cat.erase(name);  // O(1), not necessary
        } else {
            // Output highest infection cat
            if (cat_to_name.empty())
                cout << "The clinic is empty\n";
            else
                cout << cat_to_name.begin()->se << "\n";  // O(1)
        }
    }
}

### CD

- https://open.kattis.com/problems/cd

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

int n, m, ans, x;
unordered_set<int> jack;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    while (cin >> n >> m) {
        // Keep looping until input is 0 0
        if (n == 0 && m == 0) break;

        // Reset counters
        ans = 0;
        jack.clear();

        // Read input
        while (n--) {
            cin >> x;
            jack.insert(x);
        }
        while (m--) {
            cin >> x;
            if (jack.find(x) != jack.end()) ans++;
        }

        // Output answer
        cout << ans << "\n";
    }
}

### Recount

- https://open.kattis.com/problems/recount

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

#define fi first
#define se second

int most_votes, winner_count;
string name, winner;
unordered_map<string, int> candidates;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input
    while (getline(cin, name)) {
        if (name == "***") break;

        // Create new candidate entry or increase candidate's count by 1
        if (candidates.find(name) == candidates.end())
            candidates[name] = 1;
        else
            candidates[name]++;
    }

    // Find most votes
    for (auto it = candidates.begin(); it != candidates.end(); it++)
        most_votes = max(most_votes, it->se);

    // Count candidates with most_votes, get winner's name
    for (auto it = candidates.begin(); it != candidates.end(); it++) {
        if (it->se == most_votes) {
            winner = it->fi;
            winner_count++;
        }
    }

    // Output answer
    if (winner_count > 1)
        cout << "Runoff!" << endl;
    else
        cout << winner << endl;
}

### Conversation Log

- https://open.kattis.com/problems/conversationlog

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

#define fi first
#define se second

int m;
string line, name;
set<string> names;
unordered_map<string, int> word_count;
unordered_map<string, set<string>> word_to_names;
vector<string> msg;
vector<pair<int, string>> common_words;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input and a whitespace for getline to work
    cin >> m >> ws;
    for (int i = 0; i < m; i++) {
        // Read the whole input line
        getline(cin, line);

        // Clear previous msg first
        msg.clear();
        // Split whole line by whitespace, store into msg
        size_t pos = 0, next_pos;
        while ((next_pos = line.find(" ", pos)) != string::npos) {
            msg.push_back(line.substr(pos, next_pos - pos));
            pos = next_pos + 1;
        }
        msg.push_back(line.substr(pos, next_pos - pos));

        name = msg[0];
        // Keep track of a set of unique names
        names.insert(name);

        // For each word in the msg
        for (auto it = msg.begin() + 1; it != msg.end(); it++) {
            string word = *it;

            // Keep track of people who have used the word
            word_to_names[word].insert(name);

            // Update the word's count
            if (word_count.find(word) == word_count.end())
                word_count[word] = 1;
            else
                word_count[word]++;
        }
    }

    // Find common words that are mentioned by every user
    for (auto it = word_to_names.begin(); it != word_to_names.end(); it++) {
        string word = it->fi;
        int mentions = it->se.size();

        if (mentions == names.size()) {
            // Negate first value for descending order
            // Alternatively, you can define your own comparator
            common_words.push_back(make_pair(-word_count[word], word));
        }
    }

    // Sort common words
    sort(common_words.begin(), common_words.end());

    // Output answer
    if (common_words.empty())
        cout << "ALL CLEAR\n";
    else
        for (auto x : common_words) cout << x.se << "\n";
}

## Day 3 Homework

### The Easiest Problem Is This One

- https://open.kattis.com/problems/easiest

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

int n, target, ans;

// Find the sum of digit, O(# digits) i.e. O(logn)
int sum_digit(int x) {
    int result = 0;
    while (x) {
        result += x % 10;
        x /= 10;
    }
    return result;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    while (cin >> n) {
        // Terminate program when input is 0
        if (n == 0) break;

        target = sum_digit(n);

        ans = 10;
        // Keep trying new answer by increasing 1
        while (ans++) {
            if (sum_digit(n * ans) == target) {
                // Found correct answer
                cout << ans << "\n";
                break;
            }
        }
    }
}

### Watering Grass

- https://open.kattis.com/problems/grass

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

#define EPS 0.000000009

// A sprinkler has a leftmost & rightmost fully covered points
struct sp {
    double l, r;
};

bool cmp(sp a, sp b) {
    return fabs(a.l - b.l) > EPS ? a.l < b.l : a.r > b.r;
}

int n, length, width, center, radius;
vector<sp> sprinkler;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    while (cin >> n >> length >> width) {
        // Read input
        for (int i = 0; i < n; i++) {
            cin >> center >> radius;

            // Discard sprinklers that cannot fully cover the width
            if (2 * radius < width) continue;

            // Find the inner square of the circle using Pythagoras Theorem
            double dx = sqrt(pow(radius, 2) - pow((width / 2.0), 2));
            // Leftmost & rightmost fully covered points of a sprinkler
            sprinkler.push_back(sp{center - dx, center + dx});
        }

        // Sort sprinklers with ascending l, then descending r
        sort(sprinkler.begin(), sprinkler.end(), cmp);

        // Area covered (from left) so far
        double covered = 0.0;
        int ans = 0;
        bool possible = true;
        // Checking each sprinkler
        for (int i = 0; i < sprinkler.size() && possible; i++) {
            // Covered the whole grass strip
            if (covered >= length) break;
            // Discard sprinkler if its completely inside the covered area
            else if (sprinkler[i].r < covered)
                continue;
            // There is a gap that is impossible to cover with any sprinkler
            else if (sprinkler[i].l > covered)
                possible = false;
            // Given the currently "covered" point, look for sprinklers that overlaps "covered"
            // and has the largest coverage
            else {
                // Initialize the current sprinkler as the best sprinkler
                double max_right = sprinkler[i].r;
                int max_i = i;
                // Check all sprinklers that l <= covered
                while (++i < sprinkler.size() && sprinkler[i].l <= covered)
                    // Found a sprinkler that has larger coverage
                    if (sprinkler[i].r > max_right) {
                        max_right = sprinkler[i].r;
                        // Keep the max coverage sprinkler's index
                        max_i = i;
                    }
                // Set the area covered so far as the right point of the selected sprinkler
                covered = max_right;
                i = max_i;
                ans++;
            }
        }

        // Output answer
        if (!possible || covered < length)
            cout << "-1\n";
        else
            cout << ans << "\n";

        // Clear container
        sprinkler.clear();
    }
}

### The Dragon of Loowater

- https://open.kattis.com/problems/loowater

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

#define MAXN 20004

int n, m, dragon[MAXN], knight[MAXN];

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // Read input
    while (cin >> n >> m) {
        // Terminate program when input is 0 0
        if (n == 0 && m == 0) break;

        for (int i = 0; i < n; i++) cin >> dragon[i];
        for (int i = 0; i < m; i++) cin >> knight[i];

        // Sort both arrays
        sort(dragon, dragon + n);
        sort(knight, knight + m);

        // Assign each dragon to the smallest possible knight
        int k = 0, ans = 0;
        bool doomed = false;
        for (int d = 0; d < n && !doomed; d++) {
            // Finding a knight
            while (k < m && knight[k] < dragon[d]) k++;
            // Ran out of knight
            if (k == m) doomed = true;
            // Found a knight
            ans += knight[k++];
        }

        if (doomed)
            cout << "Loowater is doomed!\n";
        else
            cout << ans << "\n";
    }
}

### Traveling Monk

- https://open.kattis.com/problems/monk

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

#define MAXN 5003
#define MAXT 5000005
#define EPS 0.000001

// A segment has a height, time and cumulative time
struct Segment {
    int h, t, ct;
} asc[MAXN], dsc[MAXN];

// Get the height at a specific time, O(n)
double get_height(const Segment sg[], int n, double time) {
    // Cumulative height from previous segments
    double cum_height = 0.0;

    // Find the time's current segment
    Segment cur;
    for (int i = 0; i < n; i++) {
        cur = sg[i];
        if (time <= sg[i].ct) break;
        cum_height += sg[i].h;
    }

    // Relative time within the segment
    double rel_time = cur.t - (cur.ct - time);
    // Relative height within the segment
    double rel_height = (double)cur.h / cur.t * rel_time;

    // Real height at the given time
    return cum_height + rel_height;
}

int a, d, total_h;

int main() {
    // Read input
    cin >> a >> d;
    for (int i = 0; i < a; i++) {
        cin >> asc[i].h >> asc[i].t;
        asc[i].ct = (i == 0) ? asc[0].t : asc[i - 1].ct + asc[i].t;
        total_h += asc[i].h;
    }
    for (int i = 0; i < d; i++) {
        cin >> dsc[i].h >> dsc[i].t;
        dsc[i].ct = (i == 0) ? dsc[0].t : dsc[i - 1].ct + dsc[i].t;
    }

    // BSTA
    double lo = 0, hi = MAXT;
    while (fabs(hi - lo) > EPS) {
        double mid = (lo + hi) / 2.0;
        double asc_height = get_height(asc, a, mid);
        double dsc_height = total_h - get_height(dsc, d, mid);

        (asc_height < dsc_height) ? lo = mid : hi = mid;
    }

    // Output answer
    printf("%.6f\n", hi);
}

### Knapsack

- https://open.kattis.com/problems/knapsack

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

typedef vector<int> vi;
typedef vector<vi> vvi;

const int MAXN = 2003;

int C, n, value[MAXN], weight[MAXN];
vvi memo;

// Find the best value after considering item i with w allowed weight
int top_down(int i, int w) {
    // Previously computed state
    if (memo[i][w] != -1) return memo[i][w];

    // Base case: 0 item or no remaining weight
    if (i == 0 || w == 0) return memo[i][w] = 0;

    // If item is heavier than the bag's allowed weight, don't take it
    if (w < weight[i]) return memo[i][w] = top_down(i - 1, w);
    // Otherwise consider either taking or not taking the item
    return memo[i][w] = max(top_down(i - 1, w - weight[i]) + value[i],
                            top_down(i - 1, w));
}

// Fill the memo table using the bottom-up fashion
void bottom_up() {
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= C; w++) {
            if (i == 0 || w == 0)
                memo[i][w] = 0;
            else if (w < weight[i])
                memo[i][w] = memo[i - 1][w];
            else
                memo[i][w] = max(memo[i - 1][w - weight[i]] + value[i],
                                 memo[i - 1][w]);
        }
    }
}

// Backtrack the memo to trace which items are selected
void trace(int i, int w, vi& bag) {
    // Traced all items, job done
    if (i == 0) return;

    if (memo[i][w] == memo[i - 1][w]) {
        // Not taking item i
        return trace(i - 1, w, bag);
    } else {
        // Taking item i
        bag.push_back(i);
        return trace(i - 1, w - weight[i], bag);
    }
}

int main() {
    while (cin >> C >> n) {
        // Fast I/O
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);

        // Read input
        for (int i = 1; i <= n; i++)  // Change to 1-indexed
            cin >> value[i] >> weight[i];

        // Reset memo
        memo = vector<vi>(n + 1, vi(C + 1, -1));
        vi bag;

        // Dynamic programming
        // You may experiment by commenting away either 1 of the following 2 lines
        top_down(n, C);
        // bottom_up();
        trace(n, C, bag);

        // Output answer
        cout << bag.size() << "\n";
        for (int x : bag) cout << x - 1 << " ";  // Revert to 0-indexed
        cout << "\n";
    }
}