// https://w...content-available-to-author-only...j.com/problems/KNAPSACK/
// Top-down, dynamic programming knapsack implementation.
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <unordered_map>
using namespace std;
#define INF 1e9
// State of the problem. First: index of current element on items vector. Second: capacity remaining.
typedef pair<int, int> state;
struct Item {
int size;
int value;
};
vector<Item> items;
int N;
// Hash for using pair as key for unordered map.
struct PairHash {
size_t operator () (const state &e) const {
return (e.first * 31 + e.second);
}
};
unordered_map<state, int, PairHash> memo;
// index: index of the current item being considered in the 'items' vector.
// capacity: capacity remaining in the knapsack.
int knapsack(int index, int capacity) {
if (index == N || capacity == 0) // base cases of recursion.
return 0;
state cs = state(index, capacity); // current state of the problem.
if (memo.count(cs)) // if state already visited, return its value.
return memo[cs];
int newcap = capacity - items[index].size; // new capacity if current item is chosen.
int xa = -INF, xb; // just variables for store the recursive calls result.
xb = knapsack(index + 1, capacity); // if not to chose the current item.
if (newcap >= 0) // if current item fits in the current remaining capacity:
xa = knapsack(index + 1, newcap) + items[index].value; // value if chose the current item.
int res = max(xa, xb); // memoize and return the maximum of both possible choices.
memo[cs] = res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S;
cin >> S >> N;
items = vector<Item>(N);
for (int i = 0; i < N; i++) {
cin >> items[i].size >> items[i].value;
}
cout << knapsack(0, S) << "\n";
return 0;
}
Ly8gaHR0cHM6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5qLmNvbS9wcm9ibGVtcy9LTkFQU0FDSy8KLy8gVG9wLWRvd24sIGR5bmFtaWMgcHJvZ3JhbW1pbmcga25hcHNhY2sgaW1wbGVtZW50YXRpb24uCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDx1bm9yZGVyZWRfbWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiNkZWZpbmUgSU5GIDFlOQogCi8vIFN0YXRlIG9mIHRoZSBwcm9ibGVtLiBGaXJzdDogaW5kZXggb2YgY3VycmVudCBlbGVtZW50IG9uIGl0ZW1zIHZlY3Rvci4gU2Vjb25kOiBjYXBhY2l0eSByZW1haW5pbmcuCnR5cGVkZWYgcGFpcjxpbnQsIGludD4gc3RhdGU7ICAKIApzdHJ1Y3QgSXRlbSB7CglpbnQgc2l6ZTsKCWludCB2YWx1ZTsKfTsKIAp2ZWN0b3I8SXRlbT4gaXRlbXM7CiAKaW50IE47CgovLyBIYXNoIGZvciB1c2luZyBwYWlyIGFzIGtleSBmb3IgdW5vcmRlcmVkIG1hcC4Kc3RydWN0IFBhaXJIYXNoIHsKCXNpemVfdCBvcGVyYXRvciAoKSAoY29uc3Qgc3RhdGUgJmUpIGNvbnN0IHsKCQlyZXR1cm4gKGUuZmlyc3QgKiAzMSArIGUuc2Vjb25kKTsKCX0KfTsKCnVub3JkZXJlZF9tYXA8c3RhdGUsIGludCwgUGFpckhhc2g+IG1lbW87CiAKLy8gaW5kZXg6IGluZGV4IG9mIHRoZSBjdXJyZW50IGl0ZW0gYmVpbmcgY29uc2lkZXJlZCBpbiB0aGUgJ2l0ZW1zJyB2ZWN0b3IuCi8vIGNhcGFjaXR5OiBjYXBhY2l0eSByZW1haW5pbmcgaW4gdGhlIGtuYXBzYWNrLgppbnQga25hcHNhY2soaW50IGluZGV4LCBpbnQgY2FwYWNpdHkpIHsKCWlmIChpbmRleCA9PSBOIHx8IGNhcGFjaXR5ID09IDApICAvLyBiYXNlIGNhc2VzIG9mIHJlY3Vyc2lvbi4KCQlyZXR1cm4gMDsKCXN0YXRlIGNzID0gc3RhdGUoaW5kZXgsIGNhcGFjaXR5KTsgIC8vIGN1cnJlbnQgc3RhdGUgb2YgdGhlIHByb2JsZW0uCglpZiAobWVtby5jb3VudChjcykpICAvLyBpZiBzdGF0ZSBhbHJlYWR5IHZpc2l0ZWQsIHJldHVybiBpdHMgdmFsdWUuCgkJcmV0dXJuIG1lbW9bY3NdOwoJaW50IG5ld2NhcCA9IGNhcGFjaXR5IC0gaXRlbXNbaW5kZXhdLnNpemU7ICAgLy8gbmV3IGNhcGFjaXR5IGlmIGN1cnJlbnQgaXRlbSBpcyBjaG9zZW4uCglpbnQgeGEgPSAtSU5GLCB4YjsgIC8vIGp1c3QgdmFyaWFibGVzIGZvciBzdG9yZSB0aGUgcmVjdXJzaXZlIGNhbGxzIHJlc3VsdC4KCXhiID0ga25hcHNhY2soaW5kZXggKyAxLCBjYXBhY2l0eSk7ICAvLyBpZiBub3QgdG8gY2hvc2UgdGhlIGN1cnJlbnQgaXRlbS4KCWlmIChuZXdjYXAgPj0gMCkgIC8vIGlmIGN1cnJlbnQgaXRlbSBmaXRzIGluIHRoZSBjdXJyZW50IHJlbWFpbmluZyBjYXBhY2l0eToKCQl4YSA9IGtuYXBzYWNrKGluZGV4ICsgMSwgbmV3Y2FwKSArIGl0ZW1zW2luZGV4XS52YWx1ZTsgIC8vIHZhbHVlIGlmIGNob3NlIHRoZSBjdXJyZW50IGl0ZW0uCglpbnQgcmVzID0gbWF4KHhhLCB4Yik7ICAvLyBtZW1vaXplIGFuZCByZXR1cm4gdGhlIG1heGltdW0gb2YgYm90aCBwb3NzaWJsZSBjaG9pY2VzLgoJbWVtb1tjc10gPSByZXM7CglyZXR1cm4gcmVzOwp9CiAKIAppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luLnRpZShOVUxMKTsKIAoJaW50IFM7CgljaW4gPj4gUyA+PiBOOwoJaXRlbXMgPSB2ZWN0b3I8SXRlbT4oTik7Cglmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewoJCWNpbiA+PiBpdGVtc1tpXS5zaXplID4+IGl0ZW1zW2ldLnZhbHVlOwoJfQoJY291dCA8PCBrbmFwc2FjaygwLCBTKSA8PCAiXG4iOwogCglyZXR1cm4gMDsKfQog
MjAwMCAyMDAwCjk5IDEzCjI1IDE1Cjk3IDU0CjE5IDEwMAo2OSA4Mgo4NyA1MAoyNSA2NQo4NCA5CjYgMgo5MyA5NAo5MCAyMgozMCA5MQo3IDIxCjE5IDc0CjIxIDcKODQgMzAKMjYgNTAKNDYgMTAwCjg3IDg3CjQ3IDk4CjE2IDYyCjg4IDQ1CjU0IDMKMyAyNQo1MyA5Mwo4IDQzCjc2IDQxCjk4IDgzCjMxIDI0CjM5IDc0CjU0IDk1CjQyIDE1CjM0IDI1CjkwIDI3CjEgOTkKNTIgMzQKNjYgODIKOTkgNjIKNzAgNgo4NSA0Mwo3MiA5NAoyIDEwMAo3NSAzMwo3OSA1OAo0NiAzOQo1NyAzCjkxIDQzCjc5IDE1CjcyIDUzCjYyIDg3CjE1IDUxCjIzIDY5CjE3IDEwMAo4IDM0CjU0IDMyCjY0IDUzCjg4IDg1CjY2IDg4Cjg1IDYyCjEyIDEKOTMgNTgKNDIgODUKMzcgNTQKNzYgMzMKNjQgNDIKNzEgNDgKOTEgNTUKMTcgNTgKNzAgNzkKMjcgMzQKODkgNzMKNjUgNzQKMTYgNzQKNDYgMjEKMjMgODUKNzQgNjcKMzAgMTgKMTQgODEKMzkgMzQKMzggMTEKNDkgODkKNzkgOTAKOTYgMTYKMzEgNjUKMjQgNzYKNzkgMjMKMjggMTUKNTUgODAKNDEgODMKODAgMzIKNCAxMDAKMyAzMgo2MSA1OQoxMyA4OAo5NSA0Mgo5NCA1NQozNyA0MAoyIDIyCjU4IDE1CjMzIDI0Cjc4IDAKMjQgNTMKNzcgNDMKNTYgNzgKNDYgMjcKMTAgMzcKOTggNTMKNzcgOTgKNTkgOTYKMSA4OAo4NSA1MwozMyAzMQo4OSA4NwozMCA5Ngo1OCAwCjEwMCAxMDAKNTggNDgKNCA4CjMyIDM4Cjk1IDczCjUgNDgKNjAgNjIKNiAyNQo1NiAyMwoxOSAyMAoyMiA3Mgo0OSA3MAo5NCAxCjYxIDU0CjMyIDMKOTQgMzEKMTMgMjkKODUgNTYKNTAgNTYKNDQgMjAKODAgMgoxNSA1NQo0OSA5OQo1NyA4Nwo0OCA1NgoyIDgyCjcwIDUyCjcwIDM4CjIxIDQxCjM5IDkwCjc0IDEKOTEgNDAKMTYgNzcKNjIgMAo0OSA0OQo3MCA3Mgo2MyA0OAo4IDM5CjE5IDM0Cjg1IDkyCjMwIDU5Cjk3IDg0CjE5IDMxCjcwIDk2CjYyIDk4CjU4IDkKNjUgMzgKNDUgOTMKNzMgNzQKMzkgNzIKNzYgNDYKNzggOTgKMjIgODgKNyA3MgoxMCA1OAo1OSA0MQoyIDU0Cjc2IDgzCjQ1IDYyCjQ2IDM4CjY1IDc1CjgxIDYxCjU1IDIwCjYzIDQxCjYzIDQ4CjMgNTgKNTkgNDAKNjAgNTEKNDAgODkKMjMgMTAKMTQgNzAKNzggMzYKNzcgOTcKOTcgNDAKOTggNDQKNzUgNTAKMzkgMjQKNDEgNTgKMTAwIDk0Cjc5IDc3CjUwIDU1CjMgMTQKMTkgOTQKMzEgNjMKNTcgNwo4OSA4OAoyNiA5MAoxMiAxMgo4OSA3Nwo3MiAzNwo2NSA0Mgo1NiA4MgoyNiAxMQo1NyAyNgozMyA4NAoxMSAyNAo2NyAxNAo4MiA0NQo2NiAyCjU0IDU5CjExIDExCjYgNDcKNDggMjIKMzYgMQoxMDAgOTQKOTEgNzIKODIgMTEKOTEgMjMKNzIgMTkKMjQgNDQKNzkgMjEKMjkgNjgKOTYgOTgKMjkgNDgKODUgNDEKNTcgMTAKNTMgNTMKMTMgMTYKNTkgNzkKODEgMjgKNzcgNjUKMyAxNwo3OCA2MwozMSAxMgo4MCAyCjYyIDcyCjkxIDk5CjQyIDEwCjMyIDI3CjM2IDQ2CjY0IDgzCjU5IDU3CjYxIDcwCjY2IDMzCjQ1IDMKMzkgODAKMyAyNQo1NCAzMQo5OCA3Mgo4MiA0MAozMiAxMwo0NyAxMwo2OSA1NAo5MCAxNQo4MiA5NwoyNCA3MAo5MCA0OQo1NyA5NwozNCA4NwoxMiA2OQo1MiA1Nwo4OSA0NQo1OSAxMQoyMiA3Ngo1NiAyNAo0MyA4OQo3NiA1MQozNyA3MQo4NyA4MQoxMyAzNQo2NCA4NgozMiA3MAo4NSA3OAo2NSAzMAo1MSA0OQo3MyA5OAo5NyA4NAo5MSAyCjQ4IDg4CjMwIDk2Cjk2IDEwMAo4MyAyOQoyMiA2MgoxOSA1Mwo0MiA2CjEzIDY1Cjg2IDkwCjk1IDQwCjYyIDk0CjI0IDkzCjUwIDc3Cjc4IDIyCjY0IDYyCjY2IDUzCjI3IDkKMzUgNjkKNDEgMjIKNzAgNjYKODUgNzUKOTMgNDQKNjMgNzAKNTggNAozNCAxMwo0MSA3NAoxIDEwMAoxMDAgNDQKOTQgMzgKODEgNTgKNzMgOTIKOTQgNTAKMzcgMTcKNSA2CjcwIDE1CjExIDQKMzkgNjIKMTggNjgKNjYgMTIKNDAgOTUKODggNTQKMjcgMTAwCjU2IDkKMjIgODAKNjUgODcKNzYgODEKODEgMTgKMjQgMTAwCjUgMTMKNTIgOTIKNjAgNDMKNSAxMwoxNSAxMDAKNjIgNTcKMzcgNDIKNTIgMjcKMjkgODcKMjQgNDMKNzUgMAo2NiA5Mgo5MiAzMAozOCA0Mgo4NyA3OAo1MiA1NgoxMDAgODIKODggMjcKMTIgMwo3NSAzNAo0IDM0Cjc1IDMxCjgzIDMxCjggODYKMzAgNjQKNzQgMTQKMzAgMAo3MyAxNQo4NiAwCjkgMTkKMTUgNzYKNTcgOQo1MyAxNwoxOSA4MAo2OCA4MwoyNCA5Mgo5MSA4MAoyMCA0Cjc4IDYyCjMwIDIxCjY0IDkKMTcgODgKMTEgNDgKNzQgMzYKNDUgNTkKNTAgMjMKMzIgNDUKOTIgMzIKNzkgNTcKNzkgMzAKNDEgODkKNTkgOTEKODcgNDAKNDggMjYKOTEgNjMKOSAyNgo3MyA2NQo2OCAxNgo2OCA1NAoyNyAzNgo1MyA0OQo3MyAyNAo4MSA1NAo5MiA3NQo0MCAxMDAKMiA3NwoyMiA4Nwo1MiA0Mgo0IDI0CjMyIDIKMTAgODgKODYgNjMKNTYgMTIKMTIgMzIKNzMgNDEKODggNTgKODAgOAo2NiAyNQo1MSAzMwoxNiA1CjY5IDYzCjM5IDIwCjgzIDIzCjU2IDExCjM3IDkzCjI2IDE5CjE1IDgzCjUgODkKNjEgMzEKNDYgOTIKNDQgMQo2NyA3MQo1OSA2MAozOSA4OQo4NSA1MAo4IDI5Cjg1IDUzCjIgMTkKMSAzOQoxMyAzMwo5MSA4MgozMyA5Ngo0NyA1CjQ4IDMwCjI5IDk1CjE4IDQ3CjE1IDE3CjUgMzIKMzkgODUKNzAgMjIKMTAgNjcKMzQgMjQKMyA2NgoxMiA0NAoyMCA2NQo2MCA0OAo3IDI2CjkyIDU5CjQyIDM3CjUgNTgKNzAgNDcKMTEgNzEKNjggNjYKNiAyMQo4IDE2CjkyIDI5Cjk1IDc0CjI0IDc2CjcgODQKNDcgNTEKODMgMTEKOTQgNzMKMTIgMTIKNTAgNQo0NiAzMwoyIDEKNTkgMjYKOTIgMQo3NCAyCjMxIDgzCjQ4IDYzCjk2IDAKNDUgNTcKMzEgOTEKMzkgODkKNiA4Mgo2NCA0OAozMiA1Mgo2NiA5OQo4MCAyNwoyNSA2Mgo2OCA5CjU0IDI4CjY0IDMKNjcgMTgKMjAgNTMKNDMgMzQKMTIgOTkKOTIgNjYKMTEgNjQKOTcgODUKOTMgNjQKMTEgNjYKOTkgNgoxMCAxMAo4NyAzOAo5MiA1NQo3MSA1MwoxNCA4MQo3MSAyNAo5MiA5NwoyMiA5Mwo0OSA5MAo2MiAzMQo3OCA1Ngo2MiA5Ngo2OSAyMAoyMiA1MQo0OCAyMAo0OSA1NAo4OSA1NQo5MSAyNwo2MiA4Mwo4OCA3Mwo5NSA1Mwo3OCA1Mgo4MSAyOAoyMiAzMgo4MiA3OAo0MyA4NQo4MyAzNAozOCA0Mgo2MCA4MgozNCA3Nwo0NyA0Nwo0NyAzOAo2MSA1MAo2NyA5OAo3MSAxOAozNyAyOAo3OCA0NAo5IDU0CjYxIDI1CjgxIDM5Cjk5IDg2CjU2IDEyCjIgNjkKNzggMTkKODkgNTEKNDMgMzEKMzYgNDUKNTEgNzQKNzYgNjYKMTAwIDY0Cjk3IDkKNDIgNzkKMTggMjEKOTUgODMKNjkgNTkKNzkgMTMKNzMgMTYKNjMgNjMKNDggNzYKMTAwIDQzCjExIDE1CjUxIDMyCjEyIDgwCjgxIDUzCjE4IDczCjQgMjMKOTUgNTAKNTMgNTIKNTQgODQKNzMgNTAKOTMgNzkKMTUgMTkKNTkgNzgKNDAgOTIKNTIgNDgKNjMgNzIKNTMgMwo4MiA3MAozNyAyNAo0MyA1OQo4MCA4Ngo4NyA1OAoyNCAyNQoyNCA0NgoxMDAgNzMKOTYgNjUKMTYgNDgKNjIgNjIKNDAgMjAKNzcgNzAKNSA1NQozOCAzMQoyNyAyNgozMSAxMgo5MCAzMgoxNSAzNgo1OSA0OAo5NiAzOAoxIDc2CjEzIDI4Cjc0IDYKMzIgMzEKNDkgMjMKNjAgMTgKMSA4Ngo0NyA1Mwo4MSAxNgoyMyA0Nwo2IDczCjM0IDc5CjE3IDQ0Cjk3IDM4CjEgODgKMjcgNjQKNjIgNgoyNCA4CjMgMTUKNjIgNzEKODMgNTQKNTQgMjAKOTEgNjcKNjggNDMKNDkgMjAKNDAgMzAKODIgNDMKMzIgNwo3NCA2OAoxNSAzNgo2MSA1NgoyMyAxNQo2MCAzNAo4MSAxOAoyOCA4OAo4OCAxMwo0NyA0Mgo4NSA2NAo2MSA5Mgo1IDU1CjMzIDkyCjc0IDY5Cjk0IDIwCjU1IDE2CjY5IDg5CjcxIDUwCjU3IDYKODUgOAo4MiA3MQoyOSAyCjkwIDcwCjE0IDk4Cjk4IDkyCjY1IDM4CjY5IDgyCjc4IDIKNjMgNDcKMTUgNzMKODYgOAozNCA0MgoyMyA3MAozNCAxNAo4MyA3Nwo3MiAxCjE2IDUwCjYwIDEyCjg3IDQxCjc1IDI1CjMxIDM2CjEwMCAxCjI2IDM4CjQ5IDgxCjE2IDQyCjg1IDY5CjEwMCA3Mgo5NiA5NAo2NiA1CjgzIDIzCjI3IDczCjUwIDEKMSA3OAo4MiA5NAo1OCA3Mgo0MSA3OQoxMyAyCjU2IDUyCjM5IDUyCjkxIDUwCjg2IDM5Cjc2IDAKNTEgNzIKMjEgOTIKOTUgNjkKNjAgOTQKNjcgNwo4NiAxOAo0NiA0NQo1NiA2OQo5OSA4MAo3IDExCjg5IDc0Cjk1IDE4CjQ0IDg5CjE1IDEyCjM2IDkwCjUwIDU0Cjk3IDE4CjcwIDIzCjE5IDM5CjgzIDg5CjU5IDM1CjkgODcKODUgNjgKNDkgOQo1OSA4OAoyOCAwCjE1IDI0CjYyIDUKNTMgNTEKMzUgNTcKNTMgNTUKNzEgMwoxOSAxNgo3IDg5CjU0IDM0CjYyIDM1CjY5IDE1CjczIDg2Cjc0IDQ3Cjg2IDIyCjg0IDc1CjkzIDg2CjI2IDAKMjcgMjEKNTcgODQKNzMgMzEKNDQgMzcKOTIgMTkKNzEgMzEKODQgNjIKMzUgNjUKMjcgMzQKNzggMjEKMjEgOQo1OSAxCjQyIDcyCjEzIDU3CjkyIDg2CjMzIDQ2Cjg0IDY4CjMwIDgKMzQgNzUKNjMgMTIKOTQgOTIKMTAgNzUKOTcgOQoyNCA1OQo5IDM0CjQxIDI3CjU4IDQxCjkxIDM0Cjc0IDE1CjkwIDYzCjU3IDUzCjQgNDgKMzcgMzMKNTkgMzUKNjYgODMKNzYgMzEKNzcgNzYKOTYgMTMKNjAgNTQKMjYgMTQKMTAwIDQ0Cjk4IDMyCjI1IDEwCjg0IDI5CjY3IDI3CjQwIDUxCjI2IDk3CjE5IDMyCjQzIDIxCjI3IDc5CjgwIDY4CjMgOTcKNzQgNDcKNTkgOAo1IDgxCjcxIDUKMzAgOTcKOTAgNwoxNiA0MAo2IDI3CjQ1IDM1CjQzIDQKMzggNzcKNDIgMTgKNzEgNjMKOTUgMjAKNTYgNjgKNjcgNDIKMTQgNTQKMjIgNDUKNjAgNzcKMjYgNTgKMzAgNDYKNDggMTcKNjcgODcKMjggNDUKMjUgNzQKMjUgOTAKNzAgMjgKODMgODMKNDkgNDUKNTkgMTQKODggMzMKNTcgNTMKNTIgMzIKOTQgMjgKNzEgMzcKNzYgOTAKMzAgMjgKNzYgNTcKNzkgOTYKNTIgMTUKNDQgMzQKODggOTQKODYgNTAKNTQgMTYKMTUgNzMKMzcgNzgKOTQgMQo2IDMzCjg0IDMzCjY4IDEyCjEzIDEwMAo3NiAyOQo4NCA1NQo1NyA3MAo2OCAxMwo4NyA3MgoxOSA0MAo3MyA2OQo2NSA5Nwo3MCA2NAoyOSA5Mwo1OCAzNAoxOCA1Ngo3MCA3Mwo3MCA4NAo0MCA4Cjc2IDc4CjgwIDkzCjExIDQ4CjEwMCA4OAoyMiA5MwoyNyAxNwo3MiA1Mgo0MyA2NgoyNiAzNgoxNiA0OQo4NSA2Mwo0OCA1NwoxMiAzOQoxMDAgMjMKNDUgNTYKNTQgNjgKNzMgMjIKMjIgMzUKMyAxMDAKOTEgNDYKMTEgMzAKNzIgNQo0OCA3OQozMyAzOAo4MCAzNQo2NyA3OQo3OCA3MgoyMSA3NQozOCA4OQo1NyA3Mwo2IDY5CjgzIDI0CjQwIDE4CjM1IDUwCjEwMCAzMwoxOCAyMAo4NCA2NQo2NiA0MwoyOCA1MgozNiA1MgoxMDAgODEKMjQgNDAKNjggMTEKNiA0OAo5MSA2MQo4NyA0NAoyMyAzOQo5MyA2NAo3NSA5Ngo0NSA4Ngo0MiAxNQozMSA1MAo0NyA5MAo4IDMyCjk1IDIyCjk5IDM2CjUyIDE3CjE2IDg5CjY1IDQ1CjY4IDE1CjQzIDI5CjY3IDc4CjMwIDk5CjcwIDE1CjE5IDEwCjMgNDgKNTkgOTUKNjcgNjYKOTUgMjAKMjYgNTIKNyA5MwozOSA3MgozNSA0Nwo0MyA5Nwo2NyA3Mwo3IDYKODggMjkKMzUgMzMKNDggNTYKMzEgNAoyNCAyOQo5MyA5MQo5OSA2OQo2NiAzOAoxNyA3NQo5NiA5Nwo3OCA5MAozOCA4Mgo0MiAxMwo4IDcxCjQzIDE5CjU0IDk3CjMyIDg1CjggNDEKOTQgODUKNSA1CjIxIDgyCjU2IDIzCjY2IDYyCjc3IDQyCjY5IDc3CjIxIDE3CjExIDE2CjEyIDYxCjY1IDQKNDYgMTAKMjMgODUKNTQgNTQKNjQgOTgKNzcgMjAKMTEgNDkKMTkgMjIKNDEgMAoxNSAyMAo0MyA1NAo4NCA4CjcyIDE1CjY4IDk0CjEyIDkzCjM1IDYwCjk5IDYxCjcxIDcxCjY4IDQKMzUgNTYKNjcgMTEKMzQgNDMKOTIgMzcKMTggOTcKMTYgMTAKNDQgNTQKMTggODcKOTggMTkKOCAxCjI1IDIyCjU1IDc1CjY5IDY2CjY0IDQwCjE0IDg4Cjk4IDYxCjQ0IDkyCjg5IDcxCjU2IDU4CjcxIDI1CjggNzQKMzcgOTcKNDkgNDgKMjIgNDcKNzEgNTUKNTYgNzYKODEgMjgKMjcgMTcKMjggODMKODQgMTQKMjkgNDAKNDcgMTAKNzEgNTEKNzcgNTAKMzYgNTcKMjIgOTgKNzkgNgo1MyAxMgo3NSA1NgoxMSAyNgozMyA3Ngo3NSA0Nwo3NyA4OQo3MiA0NAozMyAyCjMwIDUxCjggNAoxMSA5NAoxOCA4OAoxMyAwCjgzIDU1CjggNTMKMiA1NQo4NCAzCjk2IDQzCjI2IDQ3CjIyIDUKODUgMzIKMiAyOAo4IDEwCjIyIDk3CjM1IDgKOTggNgo0MiA4MgoxMSA4OAoyOSA3NQo0NiA0OQo5OCA1MgozMSAyMAo4NiA4CjU3IDg1CjQgNTgKODEgMzcKODYgNTQKMjUgODgKMTEgMTgKOTUgNzAKMjEgNzIKMiAzOQo0NiAxNwo2MCA5OQozNyA4Ngo2MyA0OAo2MyAxNwo2NyA1MQo2NCA2Mgo2IDU4CjMyIDEKMzcgMjYKMTEgOTkKMzYgODAKNDcgMzQKNjcgODQKMjcgOTEKMzEgODkKNDMgMTkKNzUgOAo2NiAyNgo4IDc0CjE2IDg3CjkyIDUwCjg3IDI5CjMzIDc5CjQ1IDM4CjM3IDk1CjI4IDE3CjUxIDk1CjE4IDYKMTcgNDYKMTEgNzgKODkgOTgKOTggOTYKNDYgMTkKNzYgNjcKNjkgNjcKNDUgNTMKNyA4OAoxIDk4CjYwIDU2CjI4IDg4CjI1IDYzCjczIDQyCjM4IDMxCjkzIDI2CjQ4IDYxCjc4IDE3CjY2IDU4CjEwIDc2CjYyIDQKOTQgNzEKNTMgODcKNDYgOTgKNjQgOTkKNDEgNDIKOTUgMTQKNDAgMjgKODkgMjYKMSA5Cjc5IDY3CjcwIDgzCjU3IDEyCjEgNDgKOTYgNTIKOTUgNQozNSAwCjY5IDcyCjM3IDU2CjQ2IDk3CjI0IDQ5CjE1IDQ4CjU0IDQ0CjE3IDkyCjgwIDUzCjIzIDM0CjIxIDkyCjEwMCA1NAo3IDg3CjU5IDkwCjEwMCA4CjU3IDUzCjM0IDY1CjgwIDc3CjUyIDY0CjEzIDI0CjU3IDgyCjcxIDc1CjE4IDE3Cjg0IDM5Cjc4IDUxCjM3IDUxCjgwIDQxCjQyIDgxCjY0IDUyCjc4IDI0Cjc3IDI5CjggNTYKNTYgOTQKODUgNTcKMjYgODYKNTEgOTEKNDAgOTQKNiA0NQo3OCAyOQo3NSAyOAo3IDI2CjcyIDQ2Cjc2IDk2CjE3IDIyCjM1IDc5CjQwIDQ5CjgwIDE1CjI1IDg3CjE4IDc5CjcyIDkxCjc2IDQ1CjU3IDgyCjEwMCA0Ngo3OSA4MQo5MCAxOAoxIDcwCjQ0IDE5CjQ2IDQ4CjU4IDczCjIzIDc1CjQ4IDY0CjUyIDY5CjYwIDk1Cjg0IDcxCjQ1IDYxCjYzIDIxCjkxIDg1CjMwIDQ4Cjg2IDEyCjExIDk2Cjk3IDM2Cjg4IDI4CjIwIDMzCjUyIDgyCjc2IDY1CjM0IDgzCjY0IDM4CjMxIDgzCjY5IDI3CjY4IDQ3CjE3IDg0CjU0IDQxCjYzIDY3CjQzIDAKOTggNTIKNDYgNgoyIDUzCjQ4IDYzCjI0IDg4CjY4IDUwCjYxIDM4CjMxIDE4CjI1IDQwCjg0IDEKNTEgNjMKMjMgOAo5NyA4MAozMiA1NQoxMiA1Mwo5MiA2Ngo4MSA0MgozNSA2Mgo4MiAyMwozMSA5MQo1MiA3Nwo1NCA3Mwo2NSAzOQo5NCAwCjUwIDg4Cjg2IDMxCjEgMzcKMTYgNDAKMTcgNTgKOTggNjEKNzYgOTUKOSAxMwo3NyA5MgoyOCA5MwoyNCAzCjIwIDQ5CjgxIDI4CjIwIDk4CjcyIDEwCjc5IDU3CjggMTcKNjUgNzUKNjggMjYKNjQgMjQKODcgMTIKMjEgOQo4OSAyCjE5IDcwCjYgMzYKNDIgODkKNCA2OQo2MiA0Mgo2MSAxNAo1OSA5NgoxMCAzNwo0MSA2MAo1NSA0NAo0NCAxMQoxOCAzMwo4NCA4Mgo4MiA0NwoxOSAzNwoxNiA0MwoxOCAzNQozNSA1OQo2NSAyMwo3MiA5MQoyMCA4OAo5OSAyNgozNSA2MAozOCA4CjYgOTYKNTEgNzcKNjggNTMKNDIgODcKNjEgMTMKOTAgMwo2IDM0Cjc2IDYzCjc4IDY5Cjk3IDg1Cjk2IDE1CjQxIDY4CjcxIDk3CjMwIDUwCjYyIDE0CjU0IDYwCjg4IDcyCjMxIDY3Cjk3IDQxCjc3IDkzCjU2IDgxCjQ1IDU1CjI2IDc4CjExIDk2CjU1IDg2Cjg3IDUxCjQxIDIKMiA2MQo5OCA2NwozOSA4OAoxMDAgMzYKNDYgNjAKMzIgNDYKODUgNjQKNTAgMzQKNzQgMjgKNzggMTQKMzMgNTcKNjUgNDcKNDcgMQo1IDE2Cjg5IDE3CjQ3IDgyCjkgMzMKMzEgNTgKNTIgMjAKMzQgMQo3MCAxNgo2NiA3MQo1OCA1OQo3IDkKNjIgODQKODEgODYKMzggNDQKMSAzOAoxMDAgNDEKMTMgOTkKODIgNAo4NiA0OQo3IDQ1CjcwIDY1CjEyIDQ4CjMyIDUKNzggOTYKNzIgMjMKMjggNDUKMjEgOTYKNjYgNjMKNiA3NQoxMCA3MwoxMCA3Mwo5IDgzCjEzIDk2CjczIDQ4CjQ1IDQxCjI3IDUKNjkgNjgKMTcgNzEKNTEgOTEKNDcgNTgKMTMgMjAKODggNzEKNSA3OQoyMSA1Mgo5NyA4Nwo1NyA4Ngo5MCA3Nwo2NiA5OQo2IDEwMAo2MCA2OQozNSAxNgozNCA4OQo1OCA4Ngo2OCAzMgo4MiAzNAo4NCAxCjk4IDQwCjM2IDU4CjcgMTgKNzggOTgKNzMgNzUKNDAgNjcKNzIgODAKNzcgMjIKNDMgMjYKMTYgNjYKMjAgMzcKNDYgODgKMTcgNgo5IDU4Cjk4IDUKNDUgNjUKMTAgODgKMTEgODMKNTAgNzkKMzQgMjAKODIgOTEKMzQgNjMKMzIgMTQKMjIgMTgKNDYgMjQKNDUgOTMKNzMgMzMKNDEgMAo2MCAyOQo1MyA4OAo4MCAxOAo0MiA3MgoxNCA1MwozMyA3OQoxNSAxOAo0MyAyMQo3NyA2MQoyNiA3MAo4MiA0OAoxNSAzMwo0NyAyNAozMiA5MwoyNSA2OAo5MSA3MAo4NyA4MAo1NiA2NQo5OCA2NgoyOSAzMgo1IDE0CjI1IDUKMjIgNzgKNDUgNDMKNTUgNQozIDcwCjY1IDMKMTMgMzIKMiAzNwo2OSA3NAo5NCA2NAozMiA4Nwo2MSA3Ngo2NCA4MAo0MyA1MgoxOCA1MAo3NSA3NAozMCA5CjY3IDkzCjk2IDg4CjE4IDMxCjk3IDU2CjcgNjMKMjggMQo2MCA2OAo0OCA4MQo4MCA5OQozMSAxMAo3MSA1Mgo3MyA5NAozMSAxOQoyMyA0NQozNSA4Mwo4NyAxMDAKMjAgMTgKOTIgMjgKMjEgMjMKNDAgODEKNTEgOTEKODMgNTIKMTcgMzMKNDggNTgKNzYgMTcKODAgODcKNDQgMjMKNjAgMTEKMjUgNDcKNjEgOTQKNTIgNDkKOTYgMzMKNDAgMTAKOTAgODcKODggMTUKNyA1CjY0IDE2CjY0IDIKMjcgMjEKMTcgMzUKNTkgMTkKMTMgOTUKNzQgNTQKOTQgOTUKMzggODYKNjEgMTgKODMgMTEKNDkgNDEKNjMgNjgKMzMgNTMKMjMgMzEKNjUgNAo1NCA0CjUxIDM4CjY3IDcyCjEgNzMKODggMTcKMjQgOTYKNzYgNzAKNjYgOTIKMjcgNDgKOTEgNjUKNDYgNDcKNzkgNjIKMzcgNgoyNiA3NQo5MiA5NQo1MiA4Nwo5NCA3Nwo5OSAxMAo5NSA2MQozNCA2Nwo1NiA5NQozMSA2OAo4OCAzMwo5MSA2Nwo2NSA5CjQzIDExCjc4IDk4CjYxIDgxCjk5IDc1CjU4IDIwCjU4IDQwCjUgNgozMCA2Nwo1NyA4MAo5NiA2NAo0NSA4Mgo2NiA1NwoxMSA0Ngo5NCA2OQo2MiA2Nwo0MCA4NAoxMDAgOTEKNDQgNTUKNCA3MwozNyAzNgo4OSA3Mgo4MSAyMQo2MSA1MQo2NiA2MAo3NSA5NAo5MCAzNAo2NyA3Nwo4MyAxMwo5NSAyNAo5MSA5CjM0IDM2CjE3IDEzCjU1IDAKNjggMTcKMTggMjYKODMgMjQKNiAxMQo5IDc2Cjk2IDU0CjMwIDU0CjMxIDczCjE5IDcKNTcgODIKMTEgNjkKNjkgOTQKODEgMzQKNDkgODcKNzMgMjcKNDEgNDEKNzMgNDIKMjIgNTAKNiA2MAo1NiA0Nwo5IDY5CjYwIDEKNTAgNTgKMyA2OAo5MiA3NwoyNyA3OAo3NCA3OAoyNCAxMDAKMTQgOTMKMjkgNjYKOSAzMQoyIDY4CjU2IDE3CjM2IDc5CjI2IDgyCjcyIDM3Cjg1IDMxCjY0IDY2CjggODEKODcgNTAKMzIgMQo3MyA4Mgo0OCAyMQo4NSA4Nwo4IDU4CjE3IDE0CjMwIDcKOTYgNDcKOCAxMDAKMTkgNTIKNjggOTgKMiA1Mwo4MCAxMDAKODUgNDUKMjEgMjEKMTMgNTcKMjUgMTMKMjcgMTQKMTMgOTQKMzYgNjcKNTAgOTQKMjEgMjIKNjUgNQo1NCA0MAo3MyAyNQo5MCA4Ngo5OCA4OQoxMSAxNAo1IDg5CjEwIDU2CjE0IDMwCjg5IDg3Cjg5IDUwCjI3IDQKNjAgNTMKMTIgNjQKOTggMzUKMjUgOTIKNTAgMTQKMjAgNDQKODUgNjAKNDcgNzMKMTkgODYKMjggMjgKMSAyMgo5NSAxNQo3NSA4MQoxNSA3MQo1OSA2CjM3IDkKOTggMzUKOTIgNDAKMiA1OQo5MiAyNAoxMCA4Mwo4IDMyCjI4IDQ0CjExIDIyCjg5IDM0CjkxIDM1CjgzIDQzCjIxIDkyCjU1IDcKMjMgNTMKMTIgNDcKOTkgMTcKOTkgMTMKMzQgMjgKODQgOTIKNjAgNTgKMjkgNDAKMTcgNDMKNTMgODMKOTMgNDEKMiA2NQo2OSAxNQoyNSA2MQo2IDEKODIgNTcKNDMgNTUKNzkgOTcKNTQgNjIKMzQgNTYKNDQgNwo3MSAzNwo2OSA2Mgo4NiAzNQoxNCAzMQo4NyAzNQo0NiA0NgoyOCA1MwozNCA2NgoyMiAyNAo0NyA2Mgo1NCA5Mgo4NyA1OQozNSA3CjIyIDQKODYgMTQKMTQgMjkKOTggMjQKOTcgNTkKMjQgNzgKODQgMgoxMDAgMzgKNDkgMzEKNzEgNTcKOTMgMwo5MyA3Nwo1OSA0MQoxMyAzMAo5NyAyMAo3OSA5OQo3MSAyMAoyMyAwCjQ0IDY4CjU3IDMxCjU0IDE4CjM4IDc5CjE1IDM1CjU4IDEwCjIzIDU5CjE3IDEKNDIgNTQKNTcgMjEKNDcgODUKOTIgMTEKMjEgMQoyMyA1MAozNiA4OAo1MSA5OAo4MCA2MAo4MSA2MAoxMyA4Mwo1IDQ5CjMgMjQKMjMgMjYKMzMgNTMKOSAzMAoyMCAyMwo1NSAxOQo4MiAzNQo2NSA5CjkxIDEwCjYgNDYKMzAgNAo3MCA1NQoyMCA1NAo0OCA5Ngo3NCA2OAoxMDAgOTQKMyAzNwoyOCAyMQoyMiAzMAo0MSA0OQo2MiAyMQo1NyA3MQo1NCA5MQo0MSAyMQozIDMxCjU2IDg3CjQ3IDcxCjExIDAKNDcgMTQKNDUgNjEKNDMgODMKODIgOTkKMTMgMTAwCjI3IDYyCjM0IDk3CjM3IDIzCjg2IDQxCjcxIDc3CjE5IDY5CjkzIDk1Cjk4IDE1CjgxIDc5CjYxIDQxCjIwIDUwCjY5IDIxCjggNjkKNDYgNjcKNjAgNDgKOTUgOTkKNyA4MQoxNCAxNwo1NSA1NgoxNCAyNwo5OSA0Mwo5NCA2MgoyMiA3OAozNyA4MAo5MSA5MAo3MCA4MQo5OCA3CjY0IDgxCjg3IDIzCjEgNTcKNjEgMjkKNzUgMgo4OSA0Nwo2MiA5Ngo4MyAzCjUxIDUwCjM5IDI5CjYgMjYKNzAgODkKNDYgNDMKNzggMzYKNTMgNwoyMCAyNgoyMyA3Mgo1MyAxNgo5NCAxNAo3MCA5NQo3OSA1OAo2NSAxMgo3IDEzCjM0IDc5CjQ2IDMzCjY3IDE0CjkwIDYzCjYgNDcKMjggMzUKMTIgNDYKNTEgNzIKMSA0Mwo1OCA0OAozNSAyMQoxNCA5Mgo4NiA5Nwo1OSAyCjcxIDczCjY3IDIyCjY0IDEwMAo5OCAxNwo0MyA4Mgo5MyA4NgozNiAyNgo2NCA3MAoyNiA1NQozMCAyCjE0IDYyCjkzIDEwCjE3IDgyCjM1IDYwCjU5IDUKMSA0MQo3IDk5CjM4IDM3CjI5IDYyCjU4IDI0CjIwIDEwCjU5IDkKNTEgOTMKODAgOTAKNjMgNzcKNzAgNjcKOTUgMTIKNzEgMTcKNTQgNDQKMzIgODAKNTggMTEKMTIgNDYKNzMgNjQKNDggODIKMzMgNTgKODUgODUKMTUgNDQKNjAgNzgKNTIgNjcKMzYgMzAKMjkgMjQKOTQgNTAKNTkgNgozIDcKOTEgNzUKMTAwIDU3CjQ1IDE1CjgzIDczCjM0IDEyCjc1IDU5Cjk2IDQ4CjYzIDgzCjcgNTEKNCA1NAo3MyA4NwoxMCA4NgoxMCAzMwoyNiAyMQoxMiA1NgoxMSA1NAoxNyAyOQo2OSAxOAo3NyAxOAo3IDc0CjUzIDQyCjE3IDY5CjY4IDI2CjIwIDUxCjQxIDQyCjY2IDM5CjkgMjUKMzcgNTIKNTYgMTgKNzUgMjQKNTIgOTAKNiA4MgoxMiA2OAozMyAxNgoyIDM5Cjg0IDk0CjU0IDYzCjY2IDMxCjMxIDU5CjMgOTgKMzQgOTYKNjAgMjAKMjAgNDgKNTMgMgo4NSAzMwo5MCAxMAoyMSA3MgoxNSA0Ngo2IDE4CjIyIDEKMTQgMTYKNTYgNzcKODYgODEKMjYgNwoyNiA1NAo5NCA3NQozMSA5NQo2NyAzOAo4MyAxMQo0NCA3MAo1NCA2CjQ2IDAKMjQgNjEKODMgOQo5IDg1CjU5IDI1CjI0IDQ3CjEwMCA2NAo4NyA3Mgo1NSA1MQo1NiA2NAo5NyA1Ngo2OSA4OAo2OCAyNgoxNyA3NQo0MSA1NgoyMCA4NgozMCAyNgo2NiA1NQoyOCA2NQo0NiA4OAo5NCA1MAoyNyA0NAoxMiA4NAo4OSAzMgo3NyA0NQo2IDM5Cjc1IDIwCjI4IDMKNzMgMjgKNjYgNzYKNiAxNwo4NiA2OQo1OCA2MAoyOSA0Nwo2MyA0Mwo5OCAxNQo2OCAxMAo5MiA3MgoxOCAyMQo3MyAxMAo1OCA3OAo1IDYwCjE5IDEwCjM2IDExCjQ1IDIzCjc1IDkyCjI3IDgxCjc5IDY3CjE3IDEzCjg0IDU3CjQxIDU1Cjc0IDU5CjMyIDU0CjEwIDE2CjIxIDExCjE5IDAKNzkgMzAKNCA2Mwo3IDkwCjgzIDM5CjEzIDY5CjEwIDkwCjk1IDE1CjMxIDk4CjY3IDEwCjMzIDIwCjkwIDIwCjgwIDQ0CjgxIDY3Cjk3IDc3CjM0IDUwCjc3IDQ4CjY0IDU0CjgyIDQ4CjEgNTQKMyAzMgo2OSA5OQo1NiA4OAo3OSA2OAo1MCA1OQo1OSA1OAo1NCA1MQo1MiA0OAo3IDg2CjE5IDg4Cg==
2000 2000
99 13
25 15
97 54
19 100
69 82
87 50
25 65
84 9
6 2
93 94
90 22
30 91
7 21
19 74
21 7
84 30
26 50
46 100
87 87
47 98
16 62
88 45
54 3
3 25
53 93
8 43
76 41
98 83
31 24
39 74
54 95
42 15
34 25
90 27
1 99
52 34
66 82
99 62
70 6
85 43
72 94
2 100
75 33
79 58
46 39
57 3
91 43
79 15
72 53
62 87
15 51
23 69
17 100
8 34
54 32
64 53
88 85
66 88
85 62
12 1
93 58
42 85
37 54
76 33
64 42
71 48
91 55
17 58
70 79
27 34
89 73
65 74
16 74
46 21
23 85
74 67
30 18
14 81
39 34
38 11
49 89
79 90
96 16
31 65
24 76
79 23
28 15
55 80
41 83
80 32
4 100
3 32
61 59
13 88
95 42
94 55
37 40
2 22
58 15
33 24
78 0
24 53
77 43
56 78
46 27
10 37
98 53
77 98
59 96
1 88
85 53
33 31
89 87
30 96
58 0
100 100
58 48
4 8
32 38
95 73
5 48
60 62
6 25
56 23
19 20
22 72
49 70
94 1
61 54
32 3
94 31
13 29
85 56
50 56
44 20
80 2
15 55
49 99
57 87
48 56
2 82
70 52
70 38
21 41
39 90
74 1
91 40
16 77
62 0
49 49
70 72
63 48
8 39
19 34
85 92
30 59
97 84
19 31
70 96
62 98
58 9
65 38
45 93
73 74
39 72
76 46
78 98
22 88
7 72
10 58
59 41
2 54
76 83
45 62
46 38
65 75
81 61
55 20
63 41
63 48
3 58
59 40
60 51
40 89
23 10
14 70
78 36
77 97
97 40
98 44
75 50
39 24
41 58
100 94
79 77
50 55
3 14
19 94
31 63
57 7
89 88
26 90
12 12
89 77
72 37
65 42
56 82
26 11
57 26
33 84
11 24
67 14
82 45
66 2
54 59
11 11
6 47
48 22
36 1
100 94
91 72
82 11
91 23
72 19
24 44
79 21
29 68
96 98
29 48
85 41
57 10
53 53
13 16
59 79
81 28
77 65
3 17
78 63
31 12
80 2
62 72
91 99
42 10
32 27
36 46
64 83
59 57
61 70
66 33
45 3
39 80
3 25
54 31
98 72
82 40
32 13
47 13
69 54
90 15
82 97
24 70
90 49
57 97
34 87
12 69
52 57
89 45
59 11
22 76
56 24
43 89
76 51
37 71
87 81
13 35
64 86
32 70
85 78
65 30
51 49
73 98
97 84
91 2
48 88
30 96
96 100
83 29
22 62
19 53
42 6
13 65
86 90
95 40
62 94
24 93
50 77
78 22
64 62
66 53
27 9
35 69
41 22
70 66
85 75
93 44
63 70
58 4
34 13
41 74
1 100
100 44
94 38
81 58
73 92
94 50
37 17
5 6
70 15
11 4
39 62
18 68
66 12
40 95
88 54
27 100
56 9
22 80
65 87
76 81
81 18
24 100
5 13
52 92
60 43
5 13
15 100
62 57
37 42
52 27
29 87
24 43
75 0
66 92
92 30
38 42
87 78
52 56
100 82
88 27
12 3
75 34
4 34
75 31
83 31
8 86
30 64
74 14
30 0
73 15
86 0
9 19
15 76
57 9
53 17
19 80
68 83
24 92
91 80
20 4
78 62
30 21
64 9
17 88
11 48
74 36
45 59
50 23
32 45
92 32
79 57
79 30
41 89
59 91
87 40
48 26
91 63
9 26
73 65
68 16
68 54
27 36
53 49
73 24
81 54
92 75
40 100
2 77
22 87
52 42
4 24
32 2
10 88
86 63
56 12
12 32
73 41
88 58
80 8
66 25
51 33
16 5
69 63
39 20
83 23
56 11
37 93
26 19
15 83
5 89
61 31
46 92
44 1
67 71
59 60
39 89
85 50
8 29
85 53
2 19
1 39
13 33
91 82
33 96
47 5
48 30
29 95
18 47
15 17
5 32
39 85
70 22
10 67
34 24
3 66
12 44
20 65
60 48
7 26
92 59
42 37
5 58
70 47
11 71
68 66
6 21
8 16
92 29
95 74
24 76
7 84
47 51
83 11
94 73
12 12
50 5
46 33
2 1
59 26
92 1
74 2
31 83
48 63
96 0
45 57
31 91
39 89
6 82
64 48
32 52
66 99
80 27
25 62
68 9
54 28
64 3
67 18
20 53
43 34
12 99
92 66
11 64
97 85
93 64
11 66
99 6
10 10
87 38
92 55
71 53
14 81
71 24
92 97
22 93
49 90
62 31
78 56
62 96
69 20
22 51
48 20
49 54
89 55
91 27
62 83
88 73
95 53
78 52
81 28
22 32
82 78
43 85
83 34
38 42
60 82
34 77
47 47
47 38
61 50
67 98
71 18
37 28
78 44
9 54
61 25
81 39
99 86
56 12
2 69
78 19
89 51
43 31
36 45
51 74
76 66
100 64
97 9
42 79
18 21
95 83
69 59
79 13
73 16
63 63
48 76
100 43
11 15
51 32
12 80
81 53
18 73
4 23
95 50
53 52
54 84
73 50
93 79
15 19
59 78
40 92
52 48
63 72
53 3
82 70
37 24
43 59
80 86
87 58
24 25
24 46
100 73
96 65
16 48
62 62
40 20
77 70
5 55
38 31
27 26
31 12
90 32
15 36
59 48
96 38
1 76
13 28
74 6
32 31
49 23
60 18
1 86
47 53
81 16
23 47
6 73
34 79
17 44
97 38
1 88
27 64
62 6
24 8
3 15
62 71
83 54
54 20
91 67
68 43
49 20
40 30
82 43
32 7
74 68
15 36
61 56
23 15
60 34
81 18
28 88
88 13
47 42
85 64
61 92
5 55
33 92
74 69
94 20
55 16
69 89
71 50
57 6
85 8
82 71
29 2
90 70
14 98
98 92
65 38
69 82
78 2
63 47
15 73
86 8
34 42
23 70
34 14
83 77
72 1
16 50
60 12
87 41
75 25
31 36
100 1
26 38
49 81
16 42
85 69
100 72
96 94
66 5
83 23
27 73
50 1
1 78
82 94
58 72
41 79
13 2
56 52
39 52
91 50
86 39
76 0
51 72
21 92
95 69
60 94
67 7
86 18
46 45
56 69
99 80
7 11
89 74
95 18
44 89
15 12
36 90
50 54
97 18
70 23
19 39
83 89
59 35
9 87
85 68
49 9
59 88
28 0
15 24
62 5
53 51
35 57
53 55
71 3
19 16
7 89
54 34
62 35
69 15
73 86
74 47
86 22
84 75
93 86
26 0
27 21
57 84
73 31
44 37
92 19
71 31
84 62
35 65
27 34
78 21
21 9
59 1
42 72
13 57
92 86
33 46
84 68
30 8
34 75
63 12
94 92
10 75
97 9
24 59
9 34
41 27
58 41
91 34
74 15
90 63
57 53
4 48
37 33
59 35
66 83
76 31
77 76
96 13
60 54
26 14
100 44
98 32
25 10
84 29
67 27
40 51
26 97
19 32
43 21
27 79
80 68
3 97
74 47
59 8
5 81
71 5
30 97
90 7
16 40
6 27
45 35
43 4
38 77
42 18
71 63
95 20
56 68
67 42
14 54
22 45
60 77
26 58
30 46
48 17
67 87
28 45
25 74
25 90
70 28
83 83
49 45
59 14
88 33
57 53
52 32
94 28
71 37
76 90
30 28
76 57
79 96
52 15
44 34
88 94
86 50
54 16
15 73
37 78
94 1
6 33
84 33
68 12
13 100
76 29
84 55
57 70
68 13
87 72
19 40
73 69
65 97
70 64
29 93
58 34
18 56
70 73
70 84
40 8
76 78
80 93
11 48
100 88
22 93
27 17
72 52
43 66
26 36
16 49
85 63
48 57
12 39
100 23
45 56
54 68
73 22
22 35
3 100
91 46
11 30
72 5
48 79
33 38
80 35
67 79
78 72
21 75
38 89
57 73
6 69
83 24
40 18
35 50
100 33
18 20
84 65
66 43
28 52
36 52
100 81
24 40
68 11
6 48
91 61
87 44
23 39
93 64
75 96
45 86
42 15
31 50
47 90
8 32
95 22
99 36
52 17
16 89
65 45
68 15
43 29
67 78
30 99
70 15
19 10
3 48
59 95
67 66
95 20
26 52
7 93
39 72
35 47
43 97
67 73
7 6
88 29
35 33
48 56
31 4
24 29
93 91
99 69
66 38
17 75
96 97
78 90
38 82
42 13
8 71
43 19
54 97
32 85
8 41
94 85
5 5
21 82
56 23
66 62
77 42
69 77
21 17
11 16
12 61
65 4
46 10
23 85
54 54
64 98
77 20
11 49
19 22
41 0
15 20
43 54
84 8
72 15
68 94
12 93
35 60
99 61
71 71
68 4
35 56
67 11
34 43
92 37
18 97
16 10
44 54
18 87
98 19
8 1
25 22
55 75
69 66
64 40
14 88
98 61
44 92
89 71
56 58
71 25
8 74
37 97
49 48
22 47
71 55
56 76
81 28
27 17
28 83
84 14
29 40
47 10
71 51
77 50
36 57
22 98
79 6
53 12
75 56
11 26
33 76
75 47
77 89
72 44
33 2
30 51
8 4
11 94
18 88
13 0
83 55
8 53
2 55
84 3
96 43
26 47
22 5
85 32
2 28
8 10
22 97
35 8
98 6
42 82
11 88
29 75
46 49
98 52
31 20
86 8
57 85
4 58
81 37
86 54
25 88
11 18
95 70
21 72
2 39
46 17
60 99
37 86
63 48
63 17
67 51
64 62
6 58
32 1
37 26
11 99
36 80
47 34
67 84
27 91
31 89
43 19
75 8
66 26
8 74
16 87
92 50
87 29
33 79
45 38
37 95
28 17
51 95
18 6
17 46
11 78
89 98
98 96
46 19
76 67
69 67
45 53
7 88
1 98
60 56
28 88
25 63
73 42
38 31
93 26
48 61
78 17
66 58
10 76
62 4
94 71
53 87
46 98
64 99
41 42
95 14
40 28
89 26
1 9
79 67
70 83
57 12
1 48
96 52
95 5
35 0
69 72
37 56
46 97
24 49
15 48
54 44
17 92
80 53
23 34
21 92
100 54
7 87
59 90
100 8
57 53
34 65
80 77
52 64
13 24
57 82
71 75
18 17
84 39
78 51
37 51
80 41
42 81
64 52
78 24
77 29
8 56
56 94
85 57
26 86
51 91
40 94
6 45
78 29
75 28
7 26
72 46
76 96
17 22
35 79
40 49
80 15
25 87
18 79
72 91
76 45
57 82
100 46
79 81
90 18
1 70
44 19
46 48
58 73
23 75
48 64
52 69
60 95
84 71
45 61
63 21
91 85
30 48
86 12
11 96
97 36
88 28
20 33
52 82
76 65
34 83
64 38
31 83
69 27
68 47
17 84
54 41
63 67
43 0
98 52
46 6
2 53
48 63
24 88
68 50
61 38
31 18
25 40
84 1
51 63
23 8
97 80
32 55
12 53
92 66
81 42
35 62
82 23
31 91
52 77
54 73
65 39
94 0
50 88
86 31
1 37
16 40
17 58
98 61
76 95
9 13
77 92
28 93
24 3
20 49
81 28
20 98
72 10
79 57
8 17
65 75
68 26
64 24
87 12
21 9
89 2
19 70
6 36
42 89
4 69
62 42
61 14
59 96
10 37
41 60
55 44
44 11
18 33
84 82
82 47
19 37
16 43
18 35
35 59
65 23
72 91
20 88
99 26
35 60
38 8
6 96
51 77
68 53
42 87
61 13
90 3
6 34
76 63
78 69
97 85
96 15
41 68
71 97
30 50
62 14
54 60
88 72
31 67
97 41
77 93
56 81
45 55
26 78
11 96
55 86
87 51
41 2
2 61
98 67
39 88
100 36
46 60
32 46
85 64
50 34
74 28
78 14
33 57
65 47
47 1
5 16
89 17
47 82
9 33
31 58
52 20
34 1
70 16
66 71
58 59
7 9
62 84
81 86
38 44
1 38
100 41
13 99
82 4
86 49
7 45
70 65
12 48
32 5
78 96
72 23
28 45
21 96
66 63
6 75
10 73
10 73
9 83
13 96
73 48
45 41
27 5
69 68
17 71
51 91
47 58
13 20
88 71
5 79
21 52
97 87
57 86
90 77
66 99
6 100
60 69
35 16
34 89
58 86
68 32
82 34
84 1
98 40
36 58
7 18
78 98
73 75
40 67
72 80
77 22
43 26
16 66
20 37
46 88
17 6
9 58
98 5
45 65
10 88
11 83
50 79
34 20
82 91
34 63
32 14
22 18
46 24
45 93
73 33
41 0
60 29
53 88
80 18
42 72
14 53
33 79
15 18
43 21
77 61
26 70
82 48
15 33
47 24
32 93
25 68
91 70
87 80
56 65
98 66
29 32
5 14
25 5
22 78
45 43
55 5
3 70
65 3
13 32
2 37
69 74
94 64
32 87
61 76
64 80
43 52
18 50
75 74
30 9
67 93
96 88
18 31
97 56
7 63
28 1
60 68
48 81
80 99
31 10
71 52
73 94
31 19
23 45
35 83
87 100
20 18
92 28
21 23
40 81
51 91
83 52
17 33
48 58
76 17
80 87
44 23
60 11
25 47
61 94
52 49
96 33
40 10
90 87
88 15
7 5
64 16
64 2
27 21
17 35
59 19
13 95
74 54
94 95
38 86
61 18
83 11
49 41
63 68
33 53
23 31
65 4
54 4
51 38
67 72
1 73
88 17
24 96
76 70
66 92
27 48
91 65
46 47
79 62
37 6
26 75
92 95
52 87
94 77
99 10
95 61
34 67
56 95
31 68
88 33
91 67
65 9
43 11
78 98
61 81
99 75
58 20
58 40
5 6
30 67
57 80
96 64
45 82
66 57
11 46
94 69
62 67
40 84
100 91
44 55
4 73
37 36
89 72
81 21
61 51
66 60
75 94
90 34
67 77
83 13
95 24
91 9
34 36
17 13
55 0
68 17
18 26
83 24
6 11
9 76
96 54
30 54
31 73
19 7
57 82
11 69
69 94
81 34
49 87
73 27
41 41
73 42
22 50
6 60
56 47
9 69
60 1
50 58
3 68
92 77
27 78
74 78
24 100
14 93
29 66
9 31
2 68
56 17
36 79
26 82
72 37
85 31
64 66
8 81
87 50
32 1
73 82
48 21
85 87
8 58
17 14
30 7
96 47
8 100
19 52
68 98
2 53
80 100
85 45
21 21
13 57
25 13
27 14
13 94
36 67
50 94
21 22
65 5
54 40
73 25
90 86
98 89
11 14
5 89
10 56
14 30
89 87
89 50
27 4
60 53
12 64
98 35
25 92
50 14
20 44
85 60
47 73
19 86
28 28
1 22
95 15
75 81
15 71
59 6
37 9
98 35
92 40
2 59
92 24
10 83
8 32
28 44
11 22
89 34
91 35
83 43
21 92
55 7
23 53
12 47
99 17
99 13
34 28
84 92
60 58
29 40
17 43
53 83
93 41
2 65
69 15
25 61
6 1
82 57
43 55
79 97
54 62
34 56
44 7
71 37
69 62
86 35
14 31
87 35
46 46
28 53
34 66
22 24
47 62
54 92
87 59
35 7
22 4
86 14
14 29
98 24
97 59
24 78
84 2
100 38
49 31
71 57
93 3
93 77
59 41
13 30
97 20
79 99
71 20
23 0
44 68
57 31
54 18
38 79
15 35
58 10
23 59
17 1
42 54
57 21
47 85
92 11
21 1
23 50
36 88
51 98
80 60
81 60
13 83
5 49
3 24
23 26
33 53
9 30
20 23
55 19
82 35
65 9
91 10
6 46
30 4
70 55
20 54
48 96
74 68
100 94
3 37
28 21
22 30
41 49
62 21
57 71
54 91
41 21
3 31
56 87
47 71
11 0
47 14
45 61
43 83
82 99
13 100
27 62
34 97
37 23
86 41
71 77
19 69
93 95
98 15
81 79
61 41
20 50
69 21
8 69
46 67
60 48
95 99
7 81
14 17
55 56
14 27
99 43
94 62
22 78
37 80
91 90
70 81
98 7
64 81
87 23
1 57
61 29
75 2
89 47
62 96
83 3
51 50
39 29
6 26
70 89
46 43
78 36
53 7
20 26
23 72
53 16
94 14
70 95
79 58
65 12
7 13
34 79
46 33
67 14
90 63
6 47
28 35
12 46
51 72
1 43
58 48
35 21
14 92
86 97
59 2
71 73
67 22
64 100
98 17
43 82
93 86
36 26
64 70
26 55
30 2
14 62
93 10
17 82
35 60
59 5
1 41
7 99
38 37
29 62
58 24
20 10
59 9
51 93
80 90
63 77
70 67
95 12
71 17
54 44
32 80
58 11
12 46
73 64
48 82
33 58
85 85
15 44
60 78
52 67
36 30
29 24
94 50
59 6
3 7
91 75
100 57
45 15
83 73
34 12
75 59
96 48
63 83
7 51
4 54
73 87
10 86
10 33
26 21
12 56
11 54
17 29
69 18
77 18
7 74
53 42
17 69
68 26
20 51
41 42
66 39
9 25
37 52
56 18
75 24
52 90
6 82
12 68
33 16
2 39
84 94
54 63
66 31
31 59
3 98
34 96
60 20
20 48
53 2
85 33
90 10
21 72
15 46
6 18
22 1
14 16
56 77
86 81
26 7
26 54
94 75
31 95
67 38
83 11
44 70
54 6
46 0
24 61
83 9
9 85
59 25
24 47
100 64
87 72
55 51
56 64
97 56
69 88
68 26
17 75
41 56
20 86
30 26
66 55
28 65
46 88
94 50
27 44
12 84
89 32
77 45
6 39
75 20
28 3
73 28
66 76
6 17
86 69
58 60
29 47
63 43
98 15
68 10
92 72
18 21
73 10
58 78
5 60
19 10
36 11
45 23
75 92
27 81
79 67
17 13
84 57
41 55
74 59
32 54
10 16
21 11
19 0
79 30
4 63
7 90
83 39
13 69
10 90
95 15
31 98
67 10
33 20
90 20
80 44
81 67
97 77
34 50
77 48
64 54
82 48
1 54
3 32
69 99
56 88
79 68
50 59
59 58
54 51
52 48
7 86
19 88