One Three Nine

AtCoder

IDarc139_c

Time2000ms

Memory256MB

Difficulty—

You are given positive integers $N$ and $M$. Let us call a sequence of pairs of integers $((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K))$ **wonderful** when it satisfies the following. * $1 \le X_i \le N$ * $1 \le Y_i \le M$ * $X_i+3Y_i \neq X_j+3Y_j$ and $3X_i+Y_i \neq 3X_j+Y_j$, if $i \neq j$. Make a wonderful sequence of pairs of integers whose length, $K$, is the maximum possible. ## Constraints * $1 \le N,M \le 10^5$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ [samples]

Samples

Input #1

3 4

Output #1

10
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
3 4

For $N=3, M=4$, there is no wonderful sequence of pairs of integers whose length is $11$ or longer, and the above sequence of pairs of integers is wonderful, so this output is valid.

API Response (JSON)

{
  "problem": {
    "name": "One Three Nine",
    "description": {
      "content": "You are given positive integers $N$ and $M$. Let us call a sequence of pairs of integers $((X_1,Y_1),(X_2,Y_2),\\dots,(X_K,Y_K))$ **wonderful** when it satisfies the following. *   $1 \\le X_i \\le N$ *",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc139_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integers $N$ and $M$.\nLet us call a sequence of pairs of integers $((X_1,Y_1),(X_2,Y_2),\\dots,(X_K,Y_K))$ **wonderful** when it satisfies the following.\n\n*   $1 \\le X_i \\le N$\n*...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments