package main

import "fmt"

var N,V int
var a,v,w [1010]int

func main(){
    fmt.Scan(&N,&V)
    for i:=0;i<N;i++{
        fmt.Scan(&v[i],&w[i])
    }
    for i:=0;i<N;i++{
        for j:=1;j<=V;j++{
            t:=j-v[i]
            if t>=0 && a[t]+w[i]>a[j]{
                a[j]=a[t]+w[i]
            }
        }
    }
    fmt.Println(a[V])
}

package main

import "fmt"


var N,V int
var a,v,w [1010]int

func main(){
    fmt.Scan(&N,&V)
    for i:=0;i<N;i++{
        fmt.Scan(&v[i],&w[i])
    }
    for i:=0;i<N;i++{
        for j:=V;j>0;j--{
            t:=j-v[i]
            if t>=0 && a[t]+w[i]>a[j]{
                a[j]=a[t]+w[i]
            }
        }
    }
    fmt.Println(a[V])
}

package main

import "fmt"

const N = 1000010

var (
    n,res int
    used [N]bool
    a [N]int
    p []int
)

func main(){

    fmt.Scan(&n)
    a[1]=1
    for i:=2;i<=n;i++{
        if !used[i]{
            used[i]=true
            a[i]=i-1
            p=append(p,i)
        }

        for j:=0;p[j]*i<=n;j++{
            x:=p[j]
            used[x*i]=true
            if i%x==0{
                a[i*x]=a[i]*x
                break
            }else{
                a[i*x]=a[i]*(x-1)
            }
        }
    }
    for i:=1;i<=n;i++{
        res+=a[i]
    }
    fmt.Println(res)
}

package main

import "fmt"

var n,x,y,z int

func find()int{
    var res = 1
    for y!=0{
        if y&1==1{
            res=res*x%z
        }
        x=x*x%z
        y>>=1
    }
    return res
}

func main(){
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&x,&y,&z)
        fmt.Println(find())
    }
}

package main

import "fmt"

func find(x int) int{
    var res = x
    for i:=2;i*i<=x;i++{
        if 0==x%i{
            res = res * (i-1) / i
        }
        for ; x%i == 0 ; x/=i{}
    }
    if x!=1{
        res = res * (x-1)/x
    }
    return res
}

func main(){
    var n,x int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        fmt.Println(find(x))
    }
}

package main

import "fmt"

func gcd(a,b int)int{
    if b == 0{
        return a
    }
    return gcd(b,a%b)
}

func main(){
    var n,x,y int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&x,&y)
        if x<y{
            x,y = y,x
        }
        fmt.Println(gcd(x,y))
    }
}

package main

import "fmt"

const INF = int(1e9+7)

var (
    n,x,res int
    p map[int]int
)

func get(k,v int)(res int){
    t:=1
    for i:=0;i<=v;i++{
        res = (res + t) %INF
        t=t*k % INF
    }
    return
}
func find(x int){
    for i:=2;i*i<=x;i++{
        sum:=0
        for x%i ==0{
            x/=i
            sum++
        }
        if sum >0{
            p[i]+=sum
        }
    }
    if x!=1{
        p[x]++
    }
}

func main(){
    p =make(map[int]int)
    fmt.Scan(&n)
    res = 1
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        find(x)
    }
    res = 1
    for k,v:=range p{
        res = res*get(k,v) % INF
    }
    fmt.Println(res)
}

package main

import "fmt"

const INF = 1e9+7

var(
    n,x int
    p map[int]int
)

func find(x int){
    for i:=2;i*i<=x;i++{
        var sum int
        for x%i ==0{
            x/=i
            sum++
        }
        if sum!=0{
            p[i]+=sum
        }
    }
    if x!=1{
        p[x]++
    }
}
func main(){
    p=make(map[int]int)
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        find(x)
    }
    var res int =  1
    for _,v:=range p{
        res = res * (v+1) % int(INF)
    }
    fmt.Println(res)
}

package main

import "fmt"

func getResult(x int){
    var a []int
    for i:=1;i*i<=x;i++{
        if x%i == 0{
            fmt.Print(i," ")
            if x!=i*i {
                a=append(a,x/i)
            }
        }
    }
    for i:=len(a)-1;i>=0;i--{
        fmt.Print(a[i]," ")
    }
    fmt.Println()
}

func main(){
    var n,x int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        getResult(x)
    }
}

package main

import "fmt"

var(
    n int
    st []bool
    prima []int
)

func main(){
    fmt.Scan(&n)
    st = make([]bool,n+1)
    for i:=2;i<=n;i++{
        if !st[i]{
            prima=append(prima,i)
        }
        for _,v:=range prima{
            if v*i>n{
                break
            }
            st[v*i]=true
            if i%v == 0{
                break
            }
        }
    }
    fmt.Println(len(prima))
}